#
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