Projects per year
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.
Original language | English |
---|---|
Pages (from-to) | 1-36 |
Journal | Combinatorics, Probability and Computing |
Volume | 0 |
DOIs | |
Publication status | Published - 13 Oct 2020 |
Keywords
- 05C65
- 05C70
- 05D99
- 2020 MSC Codes:
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics
Fingerprint
Dive into the research topics of 'Covering and tiling hypergraphs with tight cycles'. Together they form a unique fingerprint.Projects
- 1 Finished
-
A graph theoretical approach for combinatorial designs
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils