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 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 R n 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. Random Struct. Alg., 44, 240‐268, 2014