Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, November 6, 2017

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005



Lecture - 14:15

Eric Fusy - LIX, Ecole Polytechnique, Paris


On Tamari intervals and planar maps

Abstract:
The Tamari lattice (in size n) is the lattice on binary trees with n nodes where the covering relation is a left rotation (at any possible node). An interval in the lattice is given by a pair of elements x,y with x<=y. Intervals of the Tamari lattice (and extensions) have a rich combinatorics initiated by Chapoton in 2006, which has been a very active area of research since then. We will present an overview of the bijective links between Tamari intervals and planar maps (graphs planarly embedded), with an emphasis on the parameter symmetries these connections reveal.



Colloquium - 16:00

Clément Requilé - Johannes Kepler University, Linz


Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture

Abstract:
A class of graphs is bridge-addable if given a graph $G$ in the class, any graph obtained by adding an edge between two connected components of $G$ is also in the class. A conjecture of McDiarmid, Steger and Welsh (2006) says that if $\cal{G}_n$ is any bridge-addable class of graphs on $n$ vertices, and $G_n$ is taken uniformly at random from $\cal{G}_n$, then $G_n$ is connected with probability at least $e^{-1/2} + o(1)$, when $n$ tends to infinity. This lower bound is asymptotically best possible since it is reached for forests, as proved by Rényi (1959).
McDiarmid, Steger and Welsh (2005) proved the lower bound of $e^{-1} + o(1)$, which was later improved to $e^{-0.7983} + o(1)$ by Balister, Bollobás and Gerke (2008), then to $e^{-2/3} + o(1)$ by Norin in an unpublished draft.
In this talk, we will discuss a proof of the conjecture, due to Chapuy and Perarnau (2015), which is based on local double-counting.




Letzte Aktualisierung: 03.11.2017