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