Andrew Treglown (University of Birmingham, U.K.) Matchings in 3-uniform hypergraphs Abstract: A theorem of Tutte characterises the graphs that have a perfect matching. In contrast, a result of Garey and Johnson implies that the decision problem whether an r-uniform hypergraph contains a perfect matching is NP-complete for r>2. So it is natural to seek simple sufficient conditions that ensure a perfect matching. Given an r-uniform hypergraph H, the degree of a k-tuple (x1,…,xk) of vertices is the number of edges in H containing x1,…,xk. The minimum vertex degree of H is the minimum of these degrees over all 1-tuples. The minimum codegree of H is the minimum of all the degrees over all (r-1)-tuples of vertices in H. In recent years there has been significant progress on this problem. In 2009, Rödl, Ruciński and Szemerédi characterised the minimum codegree that ensures a perfect matching in an r-uniform hypergraph. Much less is known about minimum vertex degree conditions for perfect matchings in r-uniform hypergraphs. In the case r=3, Hàn, Person, and Schacht asymptotically determined the minimum vertex degree that ensures a perfect matching. In this talk we discuss a result that determines this threshold exactly. (Joint work with Daniela Kühn and Deryk Osthus.) |