Exact minimum degree thresholds for perfect matchings in uniform hypergraphs

DOI10.1016/J.JCTA.2012.04.006MaRDI QIDQ439060zbMATH OpenOpenAlexFDO

Authors Andrew Treglown, Yi Zhao

Publication date 1 August 2012

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

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

zbMATH Keywords

absorbing methodhypergraph removal lemma

Mathematics Subject Classification ID

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

Abstract: Given positive integers k and r where 4 divides k and k/2 leq r leq k-1, we give a minimum r-degree condition that ensures a perfect matching in a k-uniform hypergraph. This condition is best possible and improves on work of Pikhurko who gave an asymptotically exact result. Our approach makes use of the absorbing method, as well as the hypergraph removal lemma and a structural result of Keevash and Sudakov relating to the Turan number of the expanded triangle.

Recommendations

• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
• A note on perfect matchings in uniform hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• On perfect matchings in uniform hypergraphs with large minimum vertex degree

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Applications of the regularity lemma for uniform hypergraphs
• Asymptotic solution of a Turán-type problem
• Degrees giving independent edges in a hypergraph
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Matchings in 3-uniform hypergraphs
• Matchings in hypergraphs of large minimum degree
• On a hypergraph Turán problem of Frankl
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• 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
• Perfect matchings in uniform hypergraphs with large minimum degree
• The Factorization of Linear Graphs
• Tight co-degree condition for perfect matchings in 4-graphs
• \(F\)-factors in hypergraphs via absorption

Cited in

(42)

• Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs
• A note on color-bias perfect matchings in hypergraphs
• Perfect Packings in Quasirandom Hypergraphs II
• Perfect packings in quasirandom hypergraphs. I.
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• On vertex independence number of uniform hypergraphs
• Vertex degree sums for matchings in 3-uniform hypergraphs
• Nearly perfect matchings in uniform hypergraphs
• Improved bound on vertex degree version of Erdős matching conjecture
• Packing \(k\)-partite \(k\)-uniform hypergraphs
• Vertex degree sums for matchings in 3-uniform hypergraphs
• Vertex degree sums for perfect matchings in 3-uniform hypergraphs
• Perfect matchings in 3-partite 3-uniform hypergraphs
• A note on perfect matchings in uniform hypergraphs
• \(d\)-matching in 3-uniform hypergraphs
• Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs
• Perfect matchings in hypergraphs and the Erdős matching conjecture
• Perfect matchings in uniform hypergraphs with large minimum degree
• On directed versions of the Hajnal-Szemerédi theorem
• On perfect matchings and tilings in uniform hypergraphs
• Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
• A note on exact minimum degree threshold for fractional perfect matchings
• Almost perfect matchings in \(k\)-partite \(k\)-graphs
• Perfect matchings in 4-uniform hypergraphs
• Minimum degree thresholds for Hamilton \((k/2)\)-cycles in \(k\)-uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• Matching in 3-uniform hypergraphs
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
• On perfect matchings in \(k\)-complexes
• A geometric theory for hypergraph matching
• scientific article; zbMATH DE number 5720905 (Why is no real title available?)
• On the numbers of 1-factors and 1-factorizations of hypergraphs
• Dirac-type theorems in random hypergraphs
• \(d\)-matching in \(k\)-uniform hypergraphs
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• Polynomial-time perfect matchings in dense hypergraphs
• On Hamiltonian Berge cycles in [3]-uniform hypergraphs
• Matching of given sizes in hypergraphs
• A note on minimum degree condition for Hamilton \((a,b)\)-cycles in hypergraphs

This page was built for publication: Exact minimum degree thresholds for perfect matchings in uniform hypergraphs

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