TY - JOUR
T1 - Local convergence and stability of tight bridge-addable graph classes
AU - Chapuy, Guillaume
AU - Perarnau, Guillem
PY - 2018/10/15
Y1 - 2018/10/15
N2 - 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.
AB - 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.
U2 - 10.4153/S0008414X18000020
DO - 10.4153/S0008414X18000020
M3 - Article
SN - 0008-414X
JO - Canadian Journal of Mathematics
JF - Canadian Journal of Mathematics
ER -