Paper Info
Title
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(n)))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 G(n) is connected with probability close to e(-1/2), then G(n) 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 G(n), converges in the sense of Benjamini-Schramm to the uniformly infinite random forest F-infinity. This result is reminiscent of so-called "stability results" in extremal graph theory, the difference being that here the stable extremum is not a graph but a graph class.
Year
DOI
Venue
2020
10.4153/S0008414X18000020
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES
Keywords
Field
DocType
addable class,random graph,stability,local convergence,random forest
Discrete mathematics,Random regular graph,Combinatorics,Edge-transitive graph,Vertex-transitive graph,Graph power,Cubic graph,Distance-hereditary graph,Voltage graph,Mathematics,Complement graph
Conference
Volume
Issue
ISSN
72
3
0008-414X
Citations 
PageRank 
References 
0
0.34
4
Authors
2
Name
Order
Citations
PageRank
Guillaume Chapuy17311.25
Guillem Perarnau25113.17