5 December 2012, 4:00-5:00pm

room 745, Malet Street

Perfect matchings in hypergraphs

A k-uniform hypergraph is a hypergraph in which every edge contains precisely k vertices. A perfect matching in a hypergraph H is a collection of disjoint edges which together cover all the vertices in H. A theorem of Tutte gives a characterisation of all those graphs which contain a perfect matching. On the other hand, the decision problem whether a k-uniform hypergraph contains a perfect matching is NP-complete for k>2. It is natural therefore to seek simple sufficient conditions, such as minimum degree conditions, that ensure a perfect matching in a k-uniform hypergraph. This has turned out to be a difficult question: despite considerable attention, the full solution remains elusive. In this talk I will survey recent progress on this problem, including joint work with Daniela Kühn, Deryk Osthus and Yi Zhao.