文章基本信息

标题：Local Convergence and Stability of Tight Bridge-Addable Graph Classes
本地全文：下载
作者：Guillaume Chapuy ; Guillem Perarnau
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：60
页码：26:1-26:11
DOI：10.4230/LIPIcs.APPROX-RANDOM.2016.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：bridge-addable classes; random graphs; stability; local convergence; random forests