Random graphs containing few disjoint excluded minors. Issue 2 (27th July 2012) - McDiarmid, Colin; Kurauskas, Valentas
Abstract 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb8x" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives> of graphs, as long as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb9g" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives> does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb4q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives>, there is a set B of at most g(k) vertices such that G – B is in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb58" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives>. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763–775), we showed that, amongst all graphs on vertex set <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb6t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]={1, …, n}</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb7c" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives> with 2‐connected excluded minors, as long as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sbb1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sbck" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]</alternatives> which contain at most k disjoint excluded minors for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sbd4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives>, all but an exponentially small proportion contain a set B of k vertices such that G – B is in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5w8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives>. (This is not the case when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5vq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives> contains all fans.) For a random graph Rn sampled uniformly from the graphs on <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5zc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]</alternatives> with at most k disjoint excluded minors for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5xt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />A</alternatives>, 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