Article ID Journal Published Year Pages File Type
5777122 Electronic Notes in Discrete Mathematics 2017 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,