2013/11/13 by Colin McDiarmid, McDiarmid, Colin
Computer Science · Mathematics · #05C80 #60C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Stochastic processes and statistical mechanics #math.CO #msc:05C80 #msc:60C05
paper · pdf · doi:10.48550/arxiv.1311.3240
Amplified the discussion on raising the lower bound 2/5 to 1/2
openalex publication_date 2013/11/13 · arxiv created 2016/03/01 · arxiv updated 2016/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A collection of graphs is called bridge-alterable if, for each graph G with a bridge e, G is in the class if and only if G-e is. For example the class of forests is bridge-alterable. For a random forest Fn sampled uniformly from the set of forests on vertex set 1,..,n, a classical result of Renyi (1959) shows that the probability that Fn is connected is e-1/2 +o(1). Recently Addario-Berry, McDiarmid and Reed (2012) and Kang and Panagiotou (2013) independently proved that, given a bridge-alterable class, for a random graph Rn sampled uniformly from the graphs in the class on 1,..,n, the probability that Rn is connected is at least e-1/2 +o(1). Here we give a more straightforward proof, and obtain a stronger non-asymptotic form of this result, which compares the probability to that for a random forest. We see that the probability that Rn is connected is at least the minimum over \frac25 n < t ≤ n of the probability that Ft is connected.