Contents Online

# Journal of Combinatorics

## Volume 7 (2016)

### Number 1

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

Pages: 135 – 157

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

#### Authors

#### 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