Random Graphs from a Minor-Closed Class

Source abstract

A minor-closed class of graphs is addable if each excluded minor is 2-connected. We see that such a class of labelled graphs has smooth growth; and, for the random graph R n sampled uniformly from the n -vertex graphs in , the fragment not in the giant component asymptotically has a simple ‘Boltzmann Poisson distribution’. In particular, as n → ∞ the probability that R n is connected tends to 1/ A (ρ), where A ( x ) is the exponential generating function for and ρ is its radius of convergence.