BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Connectivity in graph classes - Guillem Perarnau Llobet (Birmingha
 m)
DTSTART:20151029T143000Z
DTEND:20151029T153000Z
UID:TALK60768@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:A class of graphs is bridge-addable if\, given a graph G in th
 e class\, any graph obtained by adding an edge between two connected compo
 nents of G is also in the class. We prove a conjecture of McDiarmid\, Steg
 er and Welsh\, that says that if G_n is taken uniformly at random from a c
 lass of bridge-addable graphs on n vertices\, then G_n is connected with p
 robability at least  exp(-1/2)+o(1)\, when n tends to infinity. This lower
 \nbound is asymptotically best possible and it is reached for the class of
  forests. Our proof uses a "local double counting" strategy that enables u
 s to compare the size of two sets of combinatorial objects by solving a re
 lated multivariate optimization problem. In our case\, the optimization pr
 oblem deals with partition functions of trees weighted by a supermultiplic
 ative functional. This is joint work with Guillaume Chapuy.
LOCATION:MR12
END:VEVENT
END:VCALENDAR