When: Sunday, March 3, 10am
Where: Schreiber 309
Speaker: Kerstin Weller, Oxford
Title: Bridge-addable classes of graphs and beyond
A class of labelled graphs is called bridge-addable if for each graph in the class and each pair $u$ and $v$ of vertices in different components, the graph obtained by adding an edge joining $u$ and $v$ must also be in the class. The concept of bridge-addability was introduced by McDiarmid et al. in the course of studying random planar graphs in 2005. In my talk, I will explain the known results, particularly focusing on the probability that a uniformly random element of a finite non-empty bridge-addable class has $k$ components. Subsequently, I will generalize these results to relatively bridge-addable classes of graphs, i.e. classes of graphs where not all but only some of the possible bridges are allowed to be introduced. These results are related to the theory of expander graphs.
Joint work with Colin McDiarmid.
