2026-07-28T19:12:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6649 2024-03-06T10:38:35Z ddc:004 open_access

Local Convergence and Stability of Tight Bridge-Addable Graph Classes Chapuy, Guillaume Perarnau, Guillem bridge-addable classes random graphs stability local convergence random forests 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guillaume Chapuy and Guillem Perarnau 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.26 urn:nbn:de:0030-drops-66494 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.26 eng https://creativecommons.org/licenses/by/3.0/legalcode