University of Cambridge > Talks.cam > Combinatorics Seminar > Connectivity in graph classes

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Connectivity in graph classes

Download to your calendar using vCal

  • UserGuillem Perarnau Llobet (Birmingham)
  • ClockThursday 29 October 2015, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason .

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. We prove a conjecture of McDiarmid, Steger and Welsh, that says that if G_n is taken uniformly at random from a class of bridge-addable graphs on n vertices, then G_n is connected with probability at least exp(-1/2)+o(1), when n tends to infinity. This lower bound is asymptotically best possible and it is reached for the class of forests. Our proof uses a “local double counting” strategy that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem. In our case, the optimization problem deals with partition functions of trees weighted by a supermultiplicative functional. This is joint work with Guillaume Chapuy.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Seminar Room, Roger Needham Building, University of Cambridge https://zoom.us/j/99827103152?pwd=K0ZGZk9xSzBsSHFRbDRwZTF4dExiQT09 Zoom: https://us02web.zoom.us/webinar/register/WN_c-Wrmd12Qs20tQqM8gdTOw

Other talks

CSAR lecture: Beyond Net Zero: Can We Repair The Climate? Why people with schizophrenia die earlier? Mortality and accelerated ageing Morning Break Title and abstract tba Title to be confirmed Bacterial Physiology During Growth Arrest: Can It Be Targeted by Anti-Bacterial Therapeutics?
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity