Covering and tiling hypergraphs with tight cycles

DOI10.1016/J.ENDM.2017.07.008MaRDI QIDQ1689974zbMATH OpenOpenAlexFDO

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

Publication date 18 January 2018

Full work available at URL https://arxiv.org/abs/1701.08115, http://pure-oai.bham.ac.uk/ws/files/61007560/Han_et_al_Covering_and_tiling_hypergraphs_Combinatorics_Probability_and_Computing_2019.pdf

zbMATH Keywords

tilingcoveringhypergraphstight cyclescodegree threshold

Mathematics Subject Classification ID

Paths and cycles (05C38) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given $3leqkleqs$, we say that a $k$-uniform hypergraph $C_s^k$ is a tight cycle on $s$ vertices if there is a cyclic ordering of the vertices of $C_s^k$ such that every $k$ consecutive vertices under this ordering form an edge. We prove that if $kge3$ and $sge2k^2$, 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 $C_s^k$. Our result is asymptotically best possible for infinitely many pairs of $s$ and $k$, e.g. when $s$ and $k$ are coprime. A perfect $C_s^k$-tiling is a spanning collection of vertex-disjoint copies of $C_s^k$. When $s$ is divisible by $k$, the problem of determining the minimum codegree that guarantees a perfect $C_s^k$-tiling was solved by a result of Mycroft. We prove that if $kge3$ and $sge5k^2$ 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 $C_s^k$-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.

Recommendations

• Covering and tiling hypergraphs with tight cycles
• On tight cycles in hypergraphs
• Tight cycles in hypergraphs
• Near perfect coverings in graphs and hypergraphs
• scientific article; zbMATH DE number 4061294
• Cube tiling and covering a complete graph
• Covering Graphs by Cycles
• scientific article; zbMATH DE number 3887743
• On covering numbers of regular hypergraphs
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness

Cites work

• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A geometric theory for hypergraph matching
• Codegree thresholds for covering 3-uniform hypergraphs
• Matchings in hypergraphs of large minimum degree
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• On circuits in graphs
• On extremal problems of graphs and generalized graphs
• Packing \(k\)-partite \(k\)-uniform hypergraphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Recent advances on Dirac-type problems for hypergraphs
• \(F\)-factors in hypergraphs via absorption

Cited in

(11)

• Tight co-degree condition for packing of loose cycles in 3-graphs
• Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles
• Exact minimum codegree thresholds for \(K_4^-\)-covering and \(K_5^-\)-covering
• Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
• Covering and tiling hypergraphs with tight cycles
• Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
• Komlós's tiling theorem via graphon covers
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs
• The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
• On the minimum size of tight hypergraphs

This page was built for publication: Covering and tiling hypergraphs with tight cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1689974)