Local Convergence and Stability of Tight Bridge-addable Classes. (15th June 2020)

• Record Type: Journal Article
• Authors: Chapuy, G.; Perarnau, G.
• Is Part Of: Canadian journal of mathematics. Volume 72:Number 3(2020)
• Page Start: 563
• Page End: 601
• Publication Date: 2020-06-15
• Subjects: 05C80, -- 05C05, -- 05C40; bridge-addable class, -- random graph, -- stability, -- local convergence, -- random forest; Mathematics -- Periodicals; Mathematics; Electronic journals; Periodicals; 510
• DOI: 10.4153/S0008414X18000020
• Languages: English
• ISSNs: 0008-414X

Abstract

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 ${\mathcal{G}}$ is bridge-addable and $G_{n}$ is a uniform $n$ -vertex graph from ${\mathcal{G}}$, 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 ${\mathcal{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_{\infty }$ . 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.