2011/09/30 by Louigi Addario Berry, Colin McDiarmid, Berry, Louigi Addario +3
Computer Science · Mathematics · #60C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Stochastic processes and statistical mechanics #math.CO #msc:60C05
paper · pdf · doi:10.48550/arxiv.1110.0009
11 pages
arxiv created 2011/09/30 · openalex publication_date 2011/09/30 · arxiv updated 2011/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A class A of labelled graphs is bridge-addable if for all graphs G in A and all vertices u and v in distinct connected components of G, the graph obtained by adding an edge between u and u is also in A; the class A is monotone if for all G in A and all subgraphs H of G, H is also in A. We show that for any bridge-addable, monotone class A whose elements have vertex set 1,...,n, the probability that a uniformly random element of A is connected is at least (1-on(1)) e-1/2, where on(1) tends to zero as n tends to infinity. This establishes the special case of a conjecture of McDiarmid, Steger and Welsh when the condition of monotonicity is added. This result has also been obtained independently by Kang and Panagiotiou (2011).