Local convergence and stability of tight bridge-addable graph classes

Guillaume Chapuy, Guillem Perarnau

Research output: Contribution to journalArticlepeer-review

167 Downloads (Pure)

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 + on(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 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 n-vertex random forest in a local sense. For example, if the probability converges to e−1/2 , then Gn converges in the sense of Benjamini-Schramm to the uniformly 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.
Original languageEnglish
JournalCanadian Journal of Mathematics
Early online date15 Oct 2018
DOIs
Publication statusE-pub ahead of print - 15 Oct 2018

Fingerprint

Dive into the research topics of 'Local convergence and stability of tight bridge-addable graph classes'. Together they form a unique fingerprint.
  • Local convergence and stability of tight bridge-addable graph classes

    Chapuy, G. & Perarnau, G., Sept 2016, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Jansen, K., Mathieu, C., Rolim, J. D. P. & Umans, C. (eds.). 26

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    1 Citation (Scopus)

Cite this