# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, June 20, 2011

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

### Graphs with few disjoint cycles or t-star minors

Abstract:
The classical Erdos-Posa theorem states that in each graph G which contains at most k vertex disjoint cycles, there is a ‘blocking’ set B of O(log k) vertices such that the graph G - B is acyclic; and we may need at least c log k vertices.
We shall see 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.
As well as yielding the asymptotic number of such graphs on vertex set [n], this result lets us understand the random graph on vertex set [n] drawn from such a class. We consider 'small blockers', vertex degrees, chromatic number, and the probability of being connected.
There are corresponding counting results for graphs with at most k disjoint t-star minors (that is, with at most k vertex disjoint subtrees with t leaves) though in this case the `exceptional graphs’ may not form an exponentially small proportion.

Colloquium - 16:00

### Random graphs with few disjoint excluded minors

Abstract:
This talk supplements the earlier Colin McDiarmid's talk on graphs with few disjoint cycles.
We extend the results there for other minor-closed classes of graphs. We show for example that almost all graphs on vertex set [n] in the class of graphs with a forbidden minor k copies of a 2-connected graph H consist of a set of just k-1 vertices and a graph from Ex(H), the class of graphs with a forbidden minor H. The requirement for H is that Ex(H) does not contain all "fans".
We again consider 'small blockers', vertex degrees, chromatic number, probability of being connected, and asymptotic number of graphs on vertex set [n].

Letzte Aktualisierung: 07.06.2011