Date
Tue, 10 Nov 2009
Time
14:50 - 15:40
Location
L3
Speaker
Colin McDiarmid
Organisation
Oxford
HTML clipboard /*-->*/ /*-->*/

Fix a positive integer $k$, and consider the class of all graphs which do not have $k+1$  vertex-disjoint cycles.  A classical result of Erdos and P\'{o}sa says that each such graph $G$ contains a blocker of size at most $f(k)$.  Here a {\em blocker} is a set $B$ of vertices such that $G-B$ has no cycles.

 

We give a minor extension of this result, and deduce that almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of size $k$.  This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $R_n$ taken uniformly at random from the class: we see for example that the probability that $R_n$ is connected tends to a specified limit as $n \to \infty$.

 

There are corresponding results when we consider unlabelled graphs with few disjoint cycles. We consider also variants of the problem involving for example disjoint long cycles.

 

This is joint work with Valentas Kurauskas and Mihyun Kang.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.