Local Convergence and Stability of Tight Bridge-addable Classes

Chapuy, G. ; Perarnau, G.

Canadian journal of mathematics, Tome 72 (2020) no. 3, pp. 563-601

Résumé

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.

Détail

DOI : 10.4153/S0008414X18000020

Mots-clés : bridge-addable class, random graph, stability, local convergence, random forest

Bibliographie

[ABMR12] Addario-Berry, L., Mcdiarmid, C., and Reed, B., Connectivity for bridge-addable monotone graph classes. Combin. Probab. Comput. 21(2012), 803–815. https://doi.org/10.1017/S0963548312000272. Google Scholar

[Ald93] Aldous, D., The continuum random tree. III. Ann. Probab. 23(1993), 248–289. Google Scholar

[Ald98] Aldous, D., Tree-valued Markov chains and Poisson-Galton-Watson distributions. In: Microsurveys in discrete probability (Princeton, NJ, 1997). DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Amer. Math. Soc., Providence, RI, 199, pp. 1–20. Google Scholar

[BBG08] Balister, P., Bollobás, B., and Gerke, S., Connectivity of addable graph classes. J. Combin. Theory Ser. B 98(2008), 577–584. https://doi.org/10.1016/j.jctb.2007.09.003. Google Scholar

[BLL98] Bergeron, F., Labelle, G., and Leroux, P., Combinatorial species and tree-like structures. Encyclopedia of Mathematics and its Applications, 67, Cambridge University Press, Cambridge, 1998. Google Scholar

[BS01] Benjamini, I. and Schramm, O., Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6(2001), no. 23. Google Scholar

[CP15] Chapuy, G. and Perarnau, G., Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture. J. Combin. Theory Ser. B. https://doi.org/10.1016/j.jctb.2018.09.004. Google Scholar

[Erd66] Erdős, P., On some new inequalities concerning extremal properties of graphs. In: Theory of Graphs (Proc. Colloq., Tihany, 1966). Academic Press, New York, 1966, pp. 77–81. Google Scholar

[Erd67] Erdős, P., Some recent results on extremal problems in graph theory. In: Results, Theory of Graphs (Internat. Sympos., Rome, 1966). Gordon and Breach, New York, 1967, pp. 117–123. Google Scholar

[ES66] Erdős, P. and Simonovits, M., A limit theorem in graph theory. Studia Sci. Math. Hungar 1(1966), 51–57. Google Scholar

[FS09] Flajolet, P. and Sedgewick, R., Analytic combinatorics. Cambridge University Press, Cambridge, 2009. https://doi.org/10.1017/CBO9780511801655. Google Scholar

[KP13] Kang, M. and Panagiotou, K., On the connectivity of random graphs from addable classes. J. Combin. Theory Ser. B 103(2013), 306–312. https://doi.org/10.1016/j.jctb.2012.12.001. Google Scholar

[Lov12] Lovász, L., Large networks and graph limits. American Mathematical Society Colloquium Publications, 60, American Mathematical Society, Providence, RI, 2012. https://doi.org/10.1090/coll/060. Google Scholar

[MSW05] Mcdiarmid, C., Steger, A., and Welsh, D. J. A., Random planar graphs. J. Combin. Theory Ser. B 93(2005), 187–205. Google Scholar

[MSW06] Mcdiarmid, C., Steger, A., and Welsh, D. J. A., Random graphs from planar and other addable classes. In: Topics in discrete mathematics. Algorithms Combin., 26, Springer, Berlin, pp. 231–246. . Google Scholar | DOI

[Rén59] Rényi, A., Some remarks on the theory of trees. Magyar Tud. Akad. Mat. Kutató Int. Közl. 4(1959), 73–85. Google Scholar

[Sim68] Simonovits, M., A method for solving extremal problems in graph theory, stability problems. In: Theory of Graphs (Proc. Colloq., Tihany, 1966). Academic Press, New York, 1968, pp. 279–319. Google Scholar