BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Connectivity in graph classes - Guillem Perarnau L
lobet (Birmingham)
DTSTART;TZID=Europe/London:20151029T143000
DTEND;TZID=Europe/London:20151029T153000
UID:TALK60768AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/60768
DESCRIPTION:A class of graphs is bridge-addable if\, given a g
raph G in the class\, any graph obtained by adding
an edge between two connected components of G is
also in the class. We prove a conjecture of McDiar
mid\, Steger and Welsh\, that says that if G_n is
taken uniformly at random from a class of bridge-a
ddable graphs on n vertices\, then G_n is connecte
d with probability at least exp(-1/2)+o(1)\, when
n tends to infinity. This lower\nbound is asympto
tically best possible and it is reached for the cl
ass of forests. Our proof uses a "local double cou
nting" strategy that enables us to compare the siz
e of two sets of combinatorial objects by solving
a related multivariate optimization problem. In ou
r case\, the optimization problem deals with parti
tion functions of trees weighted by a supermultipl
icative functional. This is joint work with Guilla
ume Chapuy.
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR