Local convergence and stability of tight bridge-addable graph classes

DOI10.4230/LIPICS.APPROX-RANDOM.2016.26MaRDI QIDQ4636459zbMATH OpenOpenAlexFDO

Authors Guillaume Chapuy, Guillem Perarnau

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1609.03974

zbMATH Keywords

bridge-addable classeslocal convergencerandom forestsrandom graphsstability

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

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 $mathcalG$ is bridge-addable and $G_n$ is a uniform $n$-vertex graph from $mathcalG$, then $G_n$ is connected with probability at least $(1+o_n(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 $mathcalG$ 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 some local sense. For example, if the probability converges to $e^{-1/2}$, then $G_n$ converges in the sense of Benjamini-Schramm to the uniform infinite random forest $F_{i}nfty$. 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.

Recommendations

• Local convergence and stability of tight bridge-addable classes
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• On the connectivity of random graphs from addable classes
• Relatively Bridge-Addable Classes of Graphs

Cited in

(5)

• Combinatorial study of graphs arising from the Sachdev-Ye-Kitaev model
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Local convergence and stability of tight bridge-addable classes
• Relatively Bridge-Addable Classes of Graphs

This page was built for publication: Local convergence and stability of tight bridge-addable graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636459)