Connectivity for bridge-addable monotone graph classes
  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-o_n(1)) e^{-1/2}, where o_n(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). 
Louigi Addario Berry, Colin McDiarmid, Bruce Reed
math.CO