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

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

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

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