Random Graphs Containing Few Disjoint Excluded Minors

Journal article

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 \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. 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 \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} with 2-connected excluded minors, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} 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 \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, all but an exponentially small proportion contain a set B of k vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. (This is not the case when \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} contains all fans.) For a random graph R sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, 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.

Authors: McDiarmid, C; Kurauskas, V

• Publication status: Published
• Journal: RANDOM STRUCTURES and ALGORITHMS
• Volume: 44
• Issue: 2
• Pages: 240-268
• Publication date: 2014-03-01
• DOI: 10.1002/rsa.20447
• EISSN: 1098-2418
• ISSN: 1042-9832
• Keywords: disjoint excluded minors; fan; blocker