Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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