Perfect matchings in random hypergraphs

Series
Graph Theory Seminar
Time
Tuesday, October 13, 2020 - 3:45pm for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Matthew Kwan – Stanford University – matthew.a.kwan@gmail.comhttps://web.stanford.edu/~mattkwan/
Organizer
Anton Bernshteyn

For positive integers d<k and n divisible by k, let md(k,n) be the minimum d-degree ensuring the existence of a perfect matching in a k-uniform hypergraph. In the graph case (where k=2), a classical theorem of Dirac says that m1(2,n)=n/2. However, in general, our understanding of the values of md(k,n) is still very limited, and it is an active topic of research to determine or approximate these values. In the first part of this talk, we discuss a new "transference" theorem for Dirac-type results relative to random hypergraphs. Specifically, we prove that a random k-uniform hypergraph G with n vertices and "not too small" edge probability p typically has the property that every spanning subgraph with minimum d-degree at least (1+ε)md(k,n)p has a perfect matching. One interesting aspect of our proof is a "non-constructive" application of the absorbing method, which allows us to prove a bound in terms of md(k,n) without actually knowing its value.

The ideas in our work are quite powerful and can be applied to other problems: in the second part of this talk we highlight a recent application of these ideas to random designs, proving that a random Steiner triple system typically admits a decomposition of almost all its triples into perfect matchings (that is to say, it is almost resolvable).

Joint work with Asaf Ferber.