Near Perfect Matchings in {k}-Uniform Hypergraphs II

DOI10.1137/15M1029990MaRDI QIDQ3185658zbMATH OpenOpenAlexFDO

Authors Jie Han

Publication date 4 August 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

absorbing methodhypergraphperfect matching

Mathematics Subject Classification ID

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

Abstract: Suppose $kmidn$ and $H$ is an $n$-vertex $k$-uniform hypergraph. A near perfect matching in $H$ is a matching of size $lfloorn/kfloor$. We give a divisibility barrier construction that prevents the existence of near perfect matchings in $H$. This generalizes the divisibility barrier for perfect matchings. We give a conjecture on the minimum $d$-degree threshold forcing a (near) perfect matching in $H$ which generalizes a well-known conjecture on perfect matchings. We also verify our conjecture in various cases. Our proof makes use of the lattice-based absorbing method that the author used recently to solve two other problems on matching and tilings for hypergraphs.

Recommendations

• Near perfect matchings in \(k\)-uniform hypergraphs
• Nearly perfect matchings in uniform hypergraphs
• On the number of nearly perfect matchings in almost regular uniform hypergraphs
• A note on perfect matchings in uniform hypergraphs
• Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Matchings in \(k\)-partite \(k\)-uniform hypergraphs
• Nearly perfect matchings in regular simple hypergraphs
• Some new results on Gallai theorem and perfect matching for \(k\)-uniform hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree

Cites work

• \(F\)-factors in hypergraphs via absorption
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A geometric theory for hypergraph matching
• A note on perfect matchings in uniform hypergraphs
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• Decision problem for perfect matchings in dense k-uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Embedding large subgraphs into dense graphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• 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
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Near perfect matchings in \(k\)-uniform hypergraphs
• 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₄^3-tilings in hypergraphs of large codegree
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Perfect matchings in 4-uniform hypergraphs
• Perfect matchings in hypergraphs and the Erdős matching conjecture
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Perfect matchings in uniform hypergraphs with large minimum degree
• Polynomial-time perfect matchings in dense hypergraphs
• Recent advances on Dirac-type problems for hypergraphs
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• Tight co-degree condition for perfect matchings in 4-graphs

Cited in

(10)

• The complexity of perfect matchings and packings in dense hypergraphs
• Perfect matchings in hypergraphs and the Erdős matching conjecture
• On perfect matchings and tilings in uniform hypergraphs
• Nearly perfect matchings in uniform hypergraphs
• Matching of given sizes in hypergraphs
• Near perfect matchings in \(k\)-uniform hypergraphs
• A Ramsey–Turán theory for tilings in graphs
• Cycle-factors in oriented graphs
• H-factors in graphs with small independence number
• On the Keevash-Knox-Mycroft conjecture

This page was built for publication: Near Perfect Matchings in ${k}$-Uniform Hypergraphs II

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