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 = \Omega(n^{-k+1} \log n)$, which is asymptotically best possible. We also present similar results for Hamilton $\ell$-cycles for $\ell \geq 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 = \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.
|
