Packing k-partite k-uniform hypergraphs

DOI10.1016/J.JCTA.2015.09.007MaRDI QIDQ891826zbMATH OpenOpenAlexFDO

Authors Richard Mycroft

Publication date 17 November 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

tilinghypergraphspacking

Mathematics Subject Classification ID

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

Abstract: Let $G$ and $H$ be $k$-graphs ($k$-uniform hypergraphs); then a perfect $H$-packing in $G$ is a collection of vertex-disjoint copies of $H$ in $G$ which together cover every vertex of $G$. For any fixed $H$ let $delta(H,n)$ be the minimum $delta$ such that any $k$-graph $G$ on $n$ vertices with minimum codegree $delta(G)geqdelta$ contains a perfect $H$-packing. The problem of determining $delta(H,n)$ has been widely studied for graphs (i.e. $2$-graphs), but little is known for $kgeq3$. Here we determine the asymptotic value of $delta(H,n)$ for all complete $k$-partite $k$-graphs $H$, as well as a wide class of other $k$-partite $k$-graphs. In particular, these results provide an asymptotic solution to a question of R"odl and Ruci'nski on the value of $delta(H,n)$ when $H$ is a loose cycle. We also determine asymptotically the codegree threshold needed to guarantee an $H$-packing covering all but a constant number of vertices of $G$ for any complete $k$-partite $k$-graph $H$.

Recommendations

• Packing \(k\)-partite \(k\)-uniform hypergraphs
• Almost perfect matchings in \(k\)-partite \(k\)-graphs
• Minimum codegree condition for perfect matchings in k‐partite k‐graphs
• On a hypergraph matching problem
• Perfect packings in quasirandom hypergraphs. I.

Cites work

• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A hypergraph blow-up lemma
• A note on codegree problems for hypergraphs
• Degrees giving independent edges in a hypergraph
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• Loose Hamilton cycles in hypergraphs
• Matchings in 3-uniform hypergraphs
• Minimum codegree threshold for (K^3_4-e)-factors
• Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling
• On extremal problems of graphs and generalized graphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Perfect Packings in Quasirandom Hypergraphs II
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Perfect matchings in 3-partite 3-uniform hypergraphs
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Perfect matchings in 4-uniform hypergraphs
• Perfect matchings in \(r\)-partite \(r\)-graphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Polynomial-time perfect matchings in dense hypergraphs
• Proof of the Alon-Yuster conjecture
• Regular Partitions of Hypergraphs: Counting Lemmas
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regularity Lemma for k-uniform hypergraphs
• The minimum degree threshold for perfect graph packings
• Tight co-degree condition for perfect matchings in 4-graphs
• Tiling 3-uniform hypergraphs with \(K_4^3-2e\)
• Tiling Turán theorems
• \(F\)-factors in hypergraphs via absorption
• \(H\)-factors in dense graphs

Cited in

(25)

• Constructive packings by linear hypergraphs
• Exact minimum codegree threshold for \(K^-_4\)-factors
• Integer and fractional packings in dense 3‐uniform hypergraphs
• Covering and tiling hypergraphs with tight cycles
• Covering and tiling hypergraphs with tight cycles
• Packing \(k\)-partite \(k\)-uniform hypergraphs
• Network Capacity Bound for Personalized PageRank in Multimodal Networks
• A geometric theory for hypergraph matching
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Codegree thresholds for covering 3-uniform hypergraphs
• Tight minimum degree condition for the existence of loose cycle tilings in 3-graphs
• A note on packing of uniform hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• 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
• Sufficient conditions for perfect mixed tilings
• An asymptotic multipartite Kühn-Osthus theorem
• Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
• Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles
• Packing of nonuniform hypergrahs- product and sum of sizes conditions
• Shadows of 3-uniform hypergraphs under a minimum degree condition
• 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
• Maximally connected \(p\)-partite uniform hypergraphs

This page was built for publication: Packing \(k\)-partite \(k\)-uniform hypergraphs

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