Perfect Matchings in Dense Uniform Hypergraphs

Tuesday, October 14, 2014 - 2:00pm - 3:00pm
Lind 409
Jie Han (Georgia State University)
In graph/hypergraph theory, perfect matchings are fundamental objects of study. Unlike the graph case, perfect matchings in hypergraphs have not been well understood yet. It is quite natural and desirable to extend the classical theory on perfect matchings from graphs to hypergraphs, as many important problems can be phrased in this framework, such as Ryser's conjecture on transversals in Latin squares and the Existence Conjecture for block designs. I will focus on Dirac-type conditions (minimum degree conditions) in uniform hypergraphs and discuss some recent progresses. In particular, we determine the minimum codegree threshold for the existence of a near perfect matching in hypergraphs, which confirms a conjecture of Rödl, Ruciński and Szemerédi, and we show that there is a polynomial-time algorithm that can determine whether a k-uniform hypergraph with minimum codegree n/k has a perfect matching, which solves a problem of Karpiński, Ruciński and Szymańska completely.