Connectivity for bridge-alterable graph classes. (August 2016) - McDiarmid, Colin
Abstract: A collection A of graphs is called bridge-alterable if, for each graph G with a bridge e, G is in A if and only if G − e is. For example the class F of forests is bridge-alterable. For a random forest F n sampled uniformly from the set F n of forests on vertex set 1, …, n , a classical result of Rényi (1959) shows that the probability that F n is connected is e − 1 2 + o ( 1 ) . Recently Addario-Berry et al. (2012) and Kang and Panagiotou (2013) independently proved that, given a bridge-alterable class A, for a random graph R n sampled uniformly from the graphs in A on 1, …, n , the probability that R n 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 R n is connected is at least the minimum over 2 5 n < t ≤ n of the probability that F t is connected.