Near perfect matchings in k-uniform hypergraphs

DOI10.1017/S0963548314000613MaRDI QIDQ5364253zbMATH OpenOpenAlexFDO

Authors Jie Han

Publication date 4 October 2017

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

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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $H$ be a $k$-uniform hypergraph on $n$ vertices where $n$ is a sufficiently large integer not divisible by $k$. We prove that if the minimum $(k-1)$-degree of $H$ is at least $lfloorn/kfloor$, then $H$ contains a matching with $lfloorn/kfloor$ edges. This confirms a conjecture of R"odl, Ruci'nski and Szemer'edi, who proved that the minimum $(k-1)$-degree $n/k+O(logn)$ suffices. More generally, we show that $H$ contains a matching of size $d$ if its minimum codegree is $d<n/k$, which is also best possible.

Recommendations

• Perfect matchings in uniform hypergraphs with large minimum degree
• Nearly perfect matchings in uniform hypergraphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• Perfect matchings in large uniform hypergraphs with large minimum collective degree

Cites work

• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• 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
• 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 large uniform hypergraphs with large minimum collective degree
• Perfect matchings in uniform hypergraphs with large minimum degree
• Tight co-degree condition for perfect matchings in 4-graphs

Cited in

(28)

• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• \(d\)-matching in 3-uniform hypergraphs
• Matching in 3-uniform hypergraphs
• Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs
• On a hypergraph matching problem
• Decision problem for perfect matchings in dense k-uniform hypergraphs
• Perfect matchings in hypergraphs and the Erdős matching conjecture
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• scientific article; zbMATH DE number 5720905 (Why is no real title available?)
• On vertex independence number of uniform hypergraphs
• Proof of a tiling conjecture of Komlós
• New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
• On matchings in hypergraphs
• \(d\)-matching in \(k\)-uniform hypergraphs
• Almost perfect matchings in \(k\)-partite \(k\)-graphs
• scientific article; zbMATH DE number 1380611 (Why is no real title available?)
• Nearly perfect matchings in uniform hypergraphs
• Matching of given sizes in hypergraphs
• Matchings in \(k\)-partite \(k\)-uniform hypergraphs
• On the matching polynomial of hypergraphs
• Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
• Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
• Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
• Improved bound on vertex degree version of Erdős matching conjecture
• Matchings in multipartite hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• A note on perfect matchings in uniform hypergraphs

This page was built for publication: Near perfect matchings in \(k\)-uniform hypergraphs

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