Monday, February 6, 2017
Technische Universität Berlin
Institut für Mathematik
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Arguably, the best kind of existence theorems assert that there is the desired object unless the obvious obstacle is present. Menger's theorem is an example: either a graph contains k disjoint paths linking two vertex sets A and B or there is a set of fewer than k vertices meeting all such paths.
Such an ideal existence theorem is not always possible. The classic Erdős-Pósa theorem represents the next best type: either a graph contains k disjoint cycles or a set of O(k log k) vertices that meet every cycle. Other objects besides cycles also enjoy such an Erdős-Pósa property: for instance, there are always k disjoint subdivisions of diamonds or a bounded set of vertices meeting them all.
Edge-versions of Erdős-Pósa properties are less well known: are there always k edge-disjoint cycles or a small set of edges meeting all cycles? Yes, and this is easy. In general, however, it is less clear what objects have the edge-Erdős-Pósa property.
In the talk I will give an overview on Erdős-Pósa type theorems and discuss some recent developments.
Colloquium - 16:00
Abstract:
In 1965 Erdős and Pósa show that any graph either has many pairwise disjoint
cycles or it has a small feedback vertex set. This is known as Erdős-Pósa property.
There still is room for generalization for Erdős and Pósa property. Let H be a
fixed graph, is there any relation between the number of disjoint minor models of H
in any graph G and the size of a minimum set which hits all minor models of H in G?
This natural generalization of the Erdős-Pósa property was resolved by Robertson
and Seymour who showed that the answer to above question is positive if and only if
the graph H is planar. This in fact closed the mystery of the Erdős-Pósa property in undirected graphs.
A few years after Erdős and Pósa's great result (1973), Younger raised his famous
conjecture for directed graphs: There is a function f : ℕ -> ℕ such that for all k
and all digraphs G = (V;E), G contains k pairwise disjoint cycles or there is a set of
vertices T ⊆ V such that G-T is acyclic and the size of T is bounded from above by
f(k). Unlike undirected graphs, dealing with directed cycles was not easy and it took
about a quarter of a century for researchers to answer Younger's conjecture positively.
As for undirected graphs one can consider the more general question for digraphs:
Is there a function f : ℕ -> ℕ such that for every digraph H and for all k and every
digraphs G = (V;E), G either has k disjoint butterfly models of H or there is a set of
vertices T of size at most f(k + |H|) such that G - T has no butterfly model of H?
We answer the above question if the graph H is strongly connected by providing
a full classi cation. On the other hand we provide a characterization for vertex cyclic
graphs (the class of graphs where every vertex lies on some cycle). We show that many
natural graphs in that class do not have the Erdős and Pósa property.
(on joint work with Ken-Ichi Kawarabayashi, Stephan Kreutzer and Paul Wollan)