Journal of Combinatorics

Volume 7 (2016)

Number 1

Counting and packing Hamilton $\ell$-cycles in dense hypergraphs

Pages: 135 – 157

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n1.a6

Authors

Asaf Ferber (Department of Mathematics, Yale University, New Haven, Connecticut, U.S.A.; and Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

Michael Krivelevich (School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel)

Benny Sudakov (Department of Mathematics, ETH, Zürich, Switzerland)

Abstract

A $k$-uniform hypergraph $\mathcal{H}$ contains a Hamilton $\ell$-cycle, if there is a cyclic ordering of the vertices of $\mathcal{H}$ such that the edges of the cycle are segments of length $k$ in this ordering and any two consecutive edges $f_, f_{i+1}$ share exactly $\ell$ vertices. We consider problems about packing and counting Hamilton $\ell$-cycles in hypergraphs of large minimum degree. Given a hypergraph $\mathcal{H}$, for a $d$-subset $A \subseteq V (\mathcal{H})$, we denote by $d_{\mathcal{H}}(A)$ the number of distinct edges $f \in E (\mathcal{H})$ for which $A \subseteq f$, and set $\delta_d (\mathcal{H})$ to be the minimum $d_\mathcal{H} (A)$ over all $A \subseteq V (\mathcal{H})$ of size $d$. We show that if a $k$-uniform hypergraph on $n$ vertices $\mathcal{H}$ satisfies $\delta_{k-1} (\mathcal{H}) \geq \alpha n$ for some $\alpha \gt 1/2$, then for every $\ell \lt k/2 \mathcal{H}$ contains ${(1-o (1))}^n \cdot n! \cdot {\left ( \dfrac{\alpha}{\ell ! (k-2 \ell) !} \right )} ^{d\frac{n}{k- \ell}}$ Hamilton $\ell$-cycles. The exponent above is easily seen to be optimal. In addition, we show that if $\delta_{k-1} (\mathcal{H}) \geq \alpha n$ for $\alpha \gt 1/2$, then $\mathcal{H}$ contains $f(\alpha) n$ edge-disjoint Hamilton $\ell$-cycles for an explicit function $f(\alpha) \gt 0$. For the case where every $(k-1)$-tuple $X \subset V (\mathcal{H})$ satisfies $d_\mathcal{H} (X) \in (\alpha \pm o(1))n$, we show that $\mathcal{H}$ contains edge-disjoint Hamilton $\ell$-cycles which cover all but $o(\lvert E(\mathcal{H}) \rvert)$ edges of $\mathcal{H}$. As a tool we prove the following result which might be of independent interest: For a bipartite graph $G$ with both parts of size $n$, with minimum degree at least $\delta n$, where $\delta \gt 1/2$, and for $p = \omega (\log n/n)$ the following holds. If $G$ contains an $r$-factor for $r = \Theta(n)$, then by retaining edges of $G$ with probability $p$ independently at random, w.h.p the resulting graph contains a $(1 - o(1)) rp$-factor.

Published 9 December 2015