Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T03:38:36.996Z Has data issue: false hasContentIssue false

Covering and tiling hypergraphs with tight cycles

Published online by Cambridge University Press:  13 October 2020

Jie Han
Affiliation:
Department of Mathematics, University of Rhode Island, Kingston, RI 02881, USA
Allan Lo
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK
Nicolás Sanhueza-Matamala*
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK
*
*Corresponding author. Email: nicolas@sanhueza.net
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 \ge 2{k^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 \ge 3$, there are currently only a handful of known F-tiling results when F is k-uniform but not k-partite. If s ≢ 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 \ge 5{k^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.

Information

Type
Paper
Copyright
© The Author(s), 2020. Published by Cambridge University Press