#
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

*Abstract:*

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