Local convergence and stability of tight bridge-addable graph classes

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

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. The authors recently proved a conjecture of McDiarmid, Steger, and Welsh stating that if G is bridge-addable and Gn is a uniform n-vertex graph from G, then Gn is connected with probability at least (1 + on(1))e−1/2 . The constant e−1/2 is best possible since it is reached for the class of all forests.

In this paper we prove a form of uniqueness in this statement: if G is a bridge-addable class and the random graph Gn is connected with probability close to e−1/2 , then Gn is asymptotically close to a uniform n-vertex random forest in a local sense. For example, if the probability converges to e−1/2 , then Gn converges in the sense of Benjamini-Schramm to the uniformly infinite random forest F. This result is reminiscent of so-called “stability results” in extremal graph theory, with the difference that here the stable extremum is not a graph but a graph class.

Details

Original languageEnglish
JournalCanadian Journal of Mathematics
Early online date15 Oct 2018
Publication statusE-pub ahead of print - 15 Oct 2018