Local Convergence and Stability of Tight Bridge-Addable Graph Classes

Authors Guillaume Chapuy, Guillem Perarnau



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.26.pdf
  • Filesize: 466 kB
  • 11 pages

Document Identifiers

Author Details

Guillaume Chapuy
Guillem Perarnau

Cite AsGet BibTex

Guillaume Chapuy and Guillem Perarnau. Local Convergence and Stability of Tight Bridge-Addable Graph Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.26

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 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.
Keywords
  • bridge-addable classes
  • random graphs
  • stability
  • local convergence
  • random forests

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Louigi Addario-Berry, Colin McDiarmid, and Bruce Reed. Connectivity for bridge-addable monotone graph classes. Combin. Probab. Comput., 21(6):803-815, 2012. Google Scholar
  2. Paul Balister, Béla Bollobás, and Stefanie Gerke. Connectivity of addable graph classes. J. Combin. Theory Ser. B, 98(3):577-584, 2008. Google Scholar
  3. Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13 pp. (electronic), 2001. Google Scholar
  4. Guillaume Chapuy and Guillem Perarnau. Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture. Extended abstract in the proceedings of SODA 2016. Long version submitted for publication, see arXiv:1504.06344., 2015. Google Scholar
  5. Guillaume Chapuy and Guillem Perarnau. Local convergence and stability of tight bridge-addable graph classes. In preparation., 2016. Google Scholar
  6. Paul Erdős. On some new inequalities concerning extremal properties of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 77-81, 1966. Google Scholar
  7. Paul Erdős. Some recent results on extremal problems in graph theory. Results, Theory of Graphs (Internat. Sympos., Rome, 1966), Gordon and Breach, New York, pages 117-123, 1967. Google Scholar
  8. Paul Erdős and M Simonovits. A limit theorem in graph theory. In Studia Sci. Math. Hung. Citeseer, 1966. Google Scholar
  9. Mihyun Kang and Konstantinos Panagiotou. On the connectivity of random graphs from addable classes. J. Combin. Theory Ser. B, 103(2):306-312, 2013. Google Scholar
  10. László Lovász. Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012. Google Scholar
  11. Colin McDiarmid, Angelika Steger, and Dominic J. A. Welsh. Random graphs from planar and other addable classes. In Topics in discrete mathematics, volume 26 of Algorithms Combin., pages 231-246. Springer, Berlin, 2006. Google Scholar
  12. Alfréd Rényi. Some remarks on the theory of trees. Magyar Tud. Akad. Mat. Kutató Int. Közl., 4:73-85, 1959. Google Scholar
  13. Miklós Simonovits. A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 279-319, 1968. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail