Codegree conditions for tiling complete k-partite k-graphs and loose cycles

DOI10.1017/S096354831900021XMaRDI QIDQ5222560zbMATH OpenOpenAlexWikidataFDO

Authors Wei Gao, Jie Han, Yi Zhao

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.07247

zbMATH Keywords

Turán numbertiling loose cycles

Mathematics Subject Classification ID

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

Abstract: Given two $k$-graphs ($k$-uniform hypergraphs) $F$ and $H$, a perfect $F$-tiling (or an $F$-factor) in $H$ is a set of vertex disjoint copies of $F$ that together cover the vertex set of $H$. For all complete $k$-partite $k$-graphs $K$, Mycroft proved a minimum codegree condition that guarantees a $K$-factor in an $n$-vertex $k$-graph, which is tight up to an error term $o(n)$. In this paper we improve the error term in Mycroft's result to a sub-linear term that relates to the Tur'an number of $K$ when the differences of the sizes of the vertex classes of $K$ are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases thus disproving a conjecture of Mycroft. At last, we determine exact minimum codegree conditions for tiling $K^{(k)}(1,dots,1,2)$ and tiling loose cycles thus generalizing results of Czygrinow, DeBiasio, and Nagle, and of Czygrinow, respectively.

Recommendations

• Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
• Codegree threshold for tiling \(k\)-graphs with two edges sharing exactly \(\ell\) vertices
• Covering and tiling hypergraphs with tight cycles
• Covering and tiling hypergraphs with tight cycles
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs

Cites work

• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A geometric theory for hypergraph matching
• A hypergraph blow-up lemma
• Bombieri's theorem in short intervals
• Bounds for a Linear Diophantine Problem of Frobenius
• Counting designs
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Embedding large subgraphs into dense graphs
• Exact minimum codegree threshold for \(K^-_4\)-factors
• Forbidding just one intersection
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• Minimum codegree threshold for (K^3_4-e)-factors
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• On extremal problems of graphs and generalized graphs
• Packing \(k\)-partite \(k\)-uniform hypergraphs
• Proof of the Alon-Yuster conjecture
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
• The complexity of perfect matchings and packings in dense hypergraphs
• The minimum degree threshold for perfect graph packings
• Tight co-degree condition for packing of loose cycles in 3-graphs
• Tiling 3-uniform hypergraphs with \(K_4^3-2e\)
• Using Lovász local lemma in the space of random injections
• \(F\)-factors in hypergraphs via absorption
• \(H\)-factors in dense graphs

Cited in

(7)

• Covering and tiling hypergraphs with tight cycles
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Tiling multipartite hypergraphs in quasi-random hypergraphs
• On perfect matchings and tilings in uniform hypergraphs
• Codegree threshold for tiling \(k\)-graphs with two edges sharing exactly \(\ell\) vertices
• Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs

This page was built for publication: Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles

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