Covering and tiling hypergraphs with tight cycles

Abstract

Given $3\le k\le s$, we say that a $k$-uniform hypergraph $C_s^k$ is a tight cycle on $s$ vertices if there is a cyclic ordering of the vertices of $C_s^k$ such that every $k$ consecutive vertices under this ordering form an edge. We prove that if $k\ge 3$ and $s\ge 2k^2$, then every $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $(1/2+o(1))n$ has the property that every vertex is covered by a copy of $C_s^k$. Our result is asymptotically best possible for infinitely many pairs of $s$ and $k$, e.g. when $s$ and $k$ are coprime. A perfect $C_s^k$-tiling is a spanning collection of vertex-disjoint copies of $C_s^k$. When $s$ is divisible by $k$, the problem of determining the minimum codegree that guarantees a perfect $C_s^k$-tiling was solved by a result of Mycroft. We prove that if $k\ge 3$ and $s\ge 5k^2$ is not divisible by $k$ and $s$ divides $n$, then every $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $(1/2+1/(2s)+o(1))n$ has a perfect $C_s^k$-tiling. Again our result is asymptotically best possible for infinitely many pairs of $s$ and $k$, e.g. when $s$ and $k$ are coprime with $k$ even.

Revised version, accepted for publication in Combin. Probab. Comput

Cited by in corpus (1)

• Cycle decompositions in $k$-uniform hypergraphs