Perfect matchings in random hypergraphs

Graph Theory Seminar
Tuesday, October 13, 2020 - 3:45pm for 1 hour (actually 50 minutes)
Location For password, please email Anton Bernshteyn (bahtoh ~at~
Matthew Kwan – Stanford University – matthew.a.kwan@gmail.com
Anton Bernshteyn

For positive integers $d < k$ and $n$ divisible by $k$, let $m_d(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 $m_1(2,n) = \lceil n/2\rceil$. However, in general, our understanding of the values of $m_d(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+\varepsilon)m_d(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 $m_d(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.