TY - JOUR
T1 - Covering and tiling hypergraphs with tight cycles
AU - Han, Jie
AU - Lo, Allan
AU - Sanhueza-Matamala, Nicolás
N1 - Publisher Copyright:
© 2017 The Author(s)
PY - 2017/8
Y1 - 2017/8
N2 - Given 3≤k≤s, we say that a k-uniform hypergraph Csk is a tight cycle on s vertices if there is a cyclic ordering of the vertices of Csk such that every k consecutive vertices under this ordering form an edge. We prove that if k≥3 and s≥2k2, then every k-uniform hypergraph on n vertices with minimum codegree at least (1/2+o(1))n has the property that every vertex is covered by a copy of Csk. Our result is asymptotically best possible for infinitely many pairs of s and k, e.g. when s and k are coprime. A perfect Csk-tiling is a spanning collection of vertex-disjoint copies of Csk. When s is divisible by k, the problem of determining the minimum codegree that guarantees a perfect Csk-tiling was solved by a result of Mycroft. We prove that if k≥3 and s≥5k2 is not divisible by k and s divides n, then every k-uniform hypergraph on n vertices with minimum codegree at least (1/2+1/(2s)+o(1))n has a perfect Csk-tiling. Again our result is asymptotically best possible for infinitely many pairs of s and k, e.g. when s and k are coprime with k even.
AB - Given 3≤k≤s, we say that a k-uniform hypergraph Csk is a tight cycle on s vertices if there is a cyclic ordering of the vertices of Csk such that every k consecutive vertices under this ordering form an edge. We prove that if k≥3 and s≥2k2, then every k-uniform hypergraph on n vertices with minimum codegree at least (1/2+o(1))n has the property that every vertex is covered by a copy of Csk. Our result is asymptotically best possible for infinitely many pairs of s and k, e.g. when s and k are coprime. A perfect Csk-tiling is a spanning collection of vertex-disjoint copies of Csk. When s is divisible by k, the problem of determining the minimum codegree that guarantees a perfect Csk-tiling was solved by a result of Mycroft. We prove that if k≥3 and s≥5k2 is not divisible by k and s divides n, then every k-uniform hypergraph on n vertices with minimum codegree at least (1/2+1/(2s)+o(1))n has a perfect Csk-tiling. Again our result is asymptotically best possible for infinitely many pairs of s and k, e.g. when s and k are coprime with k even.
KW - codegree threshold
KW - covering
KW - hypergraphs
KW - tight cycles
KW - tiling
UR - http://www.scopus.com/inward/record.url?scp=85026733145&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2017.07.008
DO - 10.1016/j.endm.2017.07.008
M3 - Article
AN - SCOPUS:85026733145
SN - 1571-0653
VL - 61
SP - 561
EP - 567
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -