Covering and tiling hypergraphs with tight cycles

Research output: Contribution to journalArticle

Authors

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

Colleges, School and Institutes

Abstract

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.

Details

Original languageEnglish
JournalCombinatorics, Probability and Computing
Publication statusAccepted/In press - 5 May 2019