Random graphs containing few disjoint excluded minors

The Erd?s‐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 of graphs, as long as does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for , there is a set B of at most g(k) vertices such that G – B is in . In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763–775), we showed that, amongst all graphs on vertex set 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 with 2‐connected excluded minors, as long as 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 which contain at most k disjoint excluded minors for , all but an exponentially small proportion contain a set B of k vertices such that G – B is in . (This is not the case when contains all fans.) For a random graph R_n sampled uniformly from the graphs on with at most k disjoint excluded minors for , 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. Random Struct. Alg., 44, 240‐268, 2014