Random graphs with few disjoint cycles

Random graphs with few disjoint cycles

Tue, 10/11/2009
14:50 		Colin McDiarmid (Oxford) Combinatorial Theory Seminar Add to calendar L3
Random graphs with few disjoint cycles
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ósa says that each such graph $ G $ contains a blocker of size at most $ f(k) $.  Here a 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.