#
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**

### Colin McDiarmid -
University of Oxford

### 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**

###
Valentas Kurauskas - Vilnius University

### 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