Perfect Matchings in Dense Uniform Hypergraphs

Combinatorics Seminar
Tuesday, November 4, 2014 - 13:30
1 hour (actually 50 minutes)
Skiles 005
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 Rodl, Rucinski and Szemeredi, 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 Karpinski, Rucinski and Szymanska completely.