Dong Yeap Kang (강동엽), Hamilton cycles and optimal matchings in a random subgraph of uniform Dirac hypergraphs

A loose cycle is a cyclic ordering of edges such that every two consecutive edges share exactly one vertex. A cycle is Hamilton if it spans all vertices. A codegree of a $k$-uniform hypergraph is the minimum nonnegative integer $t$ such that every subset of vertices of size $k-1$ is contained in $t$ distinct edges.

We prove “robust” versions of Dirac-type theorems for Hamilton cycles and optimal matchings.

Let $\mathcal{H}$ be a $k$-uniform hypergraph on $n$ vertices with $n\in (k-1)\mathbb{N}$ and codegree at least $n/(2k-2)$, and let ${\mathcal{H}}_p$ be a spanning subgraph of $\mathcal{H}$ such that each edge of $\mathcal{H}$ is included in ${\mathcal{H}}_p$ with probability $p$ independently at random. We prove that a.a.s. ${\mathcal{H}}_p$ contains a loose Hamilton cycle if $p=\mathrm{\Omega }(n^{-k+1}\log n)$, which is asymptotically best possible. We also present similar results for Hamilton $\ell$-cycles for $\ell \ge 2$.

Furthermore, we prove that if $\mathcal{H}$ is a $k$-uniform hypergraph on $n$ vertices with $n\notin k\mathbb{N}$ and codegree at least $\lfloor n/k\rfloor$, then a.a.s. ${\mathcal{H}}_p$ contains a matching of size $\lfloor n/k\rfloor$ if $p=\mathrm{\Omega }(n^{-k+1}\log n)$. This is also asymptotically best possible.

This is joint work with Michael Anastos, Debsoumya Chakraborti, Abhishek Methuku, and Vincent Pfenninger.