Local Convergence and Stability of Tight Bridge-Addable Graph Classes

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 G_n is a uniform n-vertex graph from G, then G_n is connected with probability at least (1+o(1))e^{-1/2}. The constant e^{-1/2} is best possible since it is reached for the class of forests.

In this paper we prove a form of uniqueness in this statement: if G is a bridge-addable class and the random graph G_n is connected with probability close to e^{-1/2}, then G_n is asymptotically close to a uniform forest in some "local" sense. For example, if the probability converges to e^{-1/2}, then G_n converges for the Benjamini-Schramm topology, to  the uniform infinite random forest F_infinity. 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.