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

DOI10.1017/S096354831900021XzbMATH Open1436.05084arXiv1612.07247OpenAlexW2961722459WikidataQ127590474 ScholiaQ127590474MaRDI QIDQ5222560FDOQ5222560

Authors: Wei Gao, Jie Han, Yi Zhao 

Publication date: 6 April 2020

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

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.

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

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

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)

Cites Work

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