Random graphs containing few disjoint excluded minors

The Erdos-Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a 'blocking' set B of at most f(k) vertices such that the graph G - B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor-closed class A of graphs, as long as A does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for A, there is a set B of at most g(k) vertices such that G - B is in A. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763-775), we showed that, amongst all graphs on vertex set [n]={1,...,n} which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor-closed graph class A with 2-connected excluded minors, as long as A does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on [n] which contain at most k disjoint excluded minors for A, all but an exponentially small proportion contain a set B of k vertices such that G - B is in A. (This is not the case when A contains all fans.) For a random graph Rn sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for A, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc.