Covering and tiling hypergraphs with tight cycles

Author(s)

Han, Jie ^[1] ; Lo, Allan ^[2] ; Sanhueza-Matamala, Nicolas ^[2]

Affiliation

^[1] Univ Rhode Isl, Dept Math, Kingston, RI 02881 - USA

^[2] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands - England

• Document type: Journal article
• Source: COMBINATORICS PROBABILITY & COMPUTING; v. 30, n. 2, p. 288-329, MAR 2021.
• Web of Science Citations: 0

Abstract

A k-uniform tight cycle C-s(k) 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-s(k). The bound is asymptotically sharp if (k, s) is admissible. Our main tool allows us to arbitrarily rearrange the order in 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 not equivalent to 0 mod k, then C-s(k) 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-s(k)-tiling. Moreover, the bound is asymptotically sharp if k is even and (k, s) is admissible. (AU)

• FAPESP's process: 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 15/07869-8 - Perfect matchings and Tilings in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor