Monday, June 20, 2011
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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
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].