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, November 4, 2012

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

Lecture - 14:15

Peter Keevash - Oxford

Hypergraph matchings

Perfect matchings are fundamental objects of study in graph theory. There is a substantial classical theory, which cannot be directly generalised to hypergraphs unless P=NP, as it is NP-complete to determine whether a hypergraph has a perfect matching. On the other hand, the generalisation to hypergraphs is well-motivated, as many important problems can be recast in this framework, such as Ryser's conjecture on transversals in latin squares and the Erdos-Hanani conjecture on the existence of designs. We will discuss a characterisation of the perfect matching problem for uniform hypergraphs that satisfy certain density conditions (joint work with Richard Mycroft), and a polynomial time algorithm for determining whether such hypergraphs have a perfect matching (joint work with Fiachra Knox and Richard Mycroft).

Colloquium - 16:00

Alexey Pokrovskiy - Freie Universität Berlin

Covering coloured graphs by cycles

A conjecture of Erdős, Gyárfás, and Pyber says that the vertices of any r-edge-coloured complete graph can be covered by r disjoint monochromatic cycles. We will discuss several results related to this conjecture, focusing particularly on the case when there are three colours. For all r at least 3, the conjecture turns out to be false. However for r = 3 an approximate version of the conjecture holds - there is a constant c, such that every 3-edge-coloured complete graph can be covered by 3 disjoint monochromatic cycles and c extra vertices. Several related open problems and conjectures will be presented as well.

Letzte Aktualisierung: 28.10.2013