Mathematical Sciences Seminar - Perfect matchings in hypergraphs
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
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.
Contact name:
Department of Economics, Mathematics and Statistics