@inproceedings{582390e143114e8c88e17bffa4a8db1f,
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 Gn is a uniform n-vertex graph from G, then Gn 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 Gn is connected with probability close to e-1/2, then Gn is asymptotically close to a uniform forest in some {"}local{"} sense. For example, if the probability converges to e-1/2, then Gn converges for the Benjamini-Schramm topology, to the uniform 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.",
keywords = "Bridge-Addable Classes, Local Convergence, Random Forests., Random Graphs, Stability",
author = "Guillaume Chapuy and Guillem Perarnau",
year = "2016",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2016.26",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Klaus Jansen and Claire Mathieu and Rolim, \{Jose D. P.\} and Chris Umans",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016",
note = "19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 ; Conference date: 07-09-2016 Through 09-09-2016",
}