Covering and tiling hypergraphs with tight cycles

Jie Han, Allan Lo, Nicolás Sanhueza-Matamala

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)561-567
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume61
DOIs
Publication statusPublished - Aug 2017
Externally publishedYes

Keywords

  • codegree threshold
  • covering
  • hypergraphs
  • tight cycles
  • tiling

Fingerprint

Dive into the research topics of 'Covering and tiling hypergraphs with tight cycles'. Together they form a unique fingerprint.

Cite this