Combinatorics, Probability and Computing

Paper

Random Graphs with Few Disjoint Cycles

VALENTAS KURAUSKASa1 and COLIN McDIARMIDa2

a1 Vilnius University, Naugarduko 24, LT-03225 Vilnius, Lithuania (e-mail: valentas@gmail.com)

a2 Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK (e-mail: cmcd@stats.ox.ac.uk)

Abstract

The classical Erdős–Pósa theorem states that for each positive integer k there is an f(k) such that, in each graph G which does not have k + 1 disjoint cycles, there is a blocker of size at most f(k); that is, a set B of at most f(k) vertices such that GB has no cycles. We show that, amongst all such graphs on vertex set {1,. . .,n}, all but an exponentially small proportion have a blocker of size k. We also give further properties of a random graph sampled uniformly from this class, concerning uniqueness of the blocker, connectivity, chromatic number and clique number.

A key step in the proof of the main theorem is to show that there must be a blocker as in the Erdős–Pósa theorem with the extra ‘redundancy’ property that Bv is still a blocker for all but at most k vertices vB.

(Received September 20 2009)

(Revised March 28 2011)

(Online publication June 09 2011)