Covering and tiling hypergraphs with tight cycles

Jie Han, Allan Lo, Nicolás Sanhueza-Matamala

Research output: Contribution to journalArticlepeer-review

121 Downloads (Pure)


A k-uniform tight cycle C k s is a hypergraph on s > k vertices with a cyclic ordering such that every k consecutive vertices under this ordering form an edge. The pair (k, s) is admissible if gcd(k, s) = 1 or k/ gcd(k, s) is even. We prove that if s ≥ 2k 2 and H is a k-uniform hypergraph with minimum codegree at least (1/2 + o(1))|V (H)|, then every vertex is covered by a copy of C k s . The bound is asymptotically sharp if (k, s) is admissible. Our main tool allows us to arbitrarily rearrange the order of which a tight path wraps around a complete k-partite k-uniform hypergraph, which may be of independent interest. For hypergraphs F and H, a perfect F-tiling in H is a spanning collection of vertex-disjoint copies of F. For k ≥ 3, there are currently only a handful of known F-tiling results when F is k-uniform but not k-partite. If s 6≡ 0 mod k, then C k s is not k-partite. Here we prove an F-tiling result for a family of non k-partite k-uniform hypergraphs F. Namely, for s ≥ 5k 2 , every k-uniform hypergraph H with minimum codegree at least (1/2 + 1/(2s) + o(1))|V (H)| has a perfect C k s -tiling. Moreover, the bound is asymptotically sharp if k is even and (k, s) is admissible.
Original languageEnglish
Pages (from-to)1-36
JournalCombinatorics, Probability and Computing
Publication statusPublished - 13 Oct 2020


  • 05C65
  • 05C70
  • 05D99
  • 2020 MSC Codes:

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Covering and tiling hypergraphs with tight cycles'. Together they form a unique fingerprint.

Cite this