Covering and tiling hypergraphs with tight cycles
Research output: Contribution to journal › Article
Colleges, School and Institutes
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.
|Journal||Combinatorics, Probability and Computing|
|Publication status||Accepted/In press - 5 May 2019|