Connectivity for bridge-alterable graph classes. (August 2016)

• Record Type: Journal Article
• Authors: McDiarmid, Colin
• Is Part Of: European journal of combinatorics. Volume 56(2016:Aug.)
• Page Start: 33
• Page End: 39
• Publication Date: 2016-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.02.007
• Languages: English
• ISSNs: 0195-6698

Abstract

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.