|
Random graphs with few disjoint cycles| old_uid | 7559 |
|---|
| title | Random graphs with few disjoint cycles |
|---|
| start_date | 2009/11/09 |
|---|
| schedule | 13h30 |
|---|
| online | no |
|---|
| location_info | V106 |
|---|
| summary | 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 Posa 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,...,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 tends to infinity.
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. |
|---|
| responsibles | Biau, Stoltz, Massart |
|---|
| |
|