Matching of given sizes in hypergraphs

DOI10.1137/21M1430327MaRDI QIDQ5043636zbMATH OpenFDO

Authors Yu-Lin Chang, Huifen Ge, Jie Han, Guanghui Wang

Publication date 6 October 2022

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

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

zbMATH Keywords

matchingabsorbing methodhypergraph

Mathematics Subject Classification ID

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

Abstract: For all integers $k,d$ such that $kgeq3$ and $k/2leqdleqk-1$, let $n$ be a sufficiently large integer { m(}which may not be divisible by $k${ m)} and let $slelfloorn/kfloor-1$. We show that if $H$ is a $k$-uniform hypergraph on $n$ vertices with $$, then $H$ contains a matching of size $s$. This improves a recent result of Lu, Yu, and Yuan and also answers a question of K"uhn, Osthus, and Townsend. In many cases, our result can be strengthened to $sleqlfloorn/kfloor$, which then covers the entire possible range of $s$. On the other hand, there are examples showing that the result does not hold for certain $n,k,d$ and $s=lfloorn/kfloor$.

Recommendations

• \(d\)-matching in \(k\)-uniform hypergraphs
• Nearly perfect matchings in uniform hypergraphs
• Near perfect matchings in \(k\)-uniform hypergraphs
• Matching in 3-uniform hypergraphs
• On matchings in hypergraphs

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
• 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
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• Near perfect matchings in \(k\)-uniform hypergraphs
• Nearly perfect matchings in uniform hypergraphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Paths, Trees, and Flowers
• 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-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
• Recent advances on Dirac-type problems for hypergraphs
• Reducibility among combinatorial problems
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• The Erdős matching conjecture and concentration inequalities
• The Factorization of Linear Graphs
• The complexity of perfect matchings and packings in dense hypergraphs
• Tight co-degree condition for perfect matchings in 4-graphs

Cited in

(8)

• Matchings in hypergraphs of large minimum degree
• Santa Claus Meets Hypergraph Matchings
• Disjoint perfect matchings in 3‐uniform hypergraphs
• Matching orderable and separable hypergraphs
• Santa claus meets hypergraph matchings
• \(d\)-matching in \(k\)-uniform hypergraphs
• Matchings in \(k\)-partite \(k\)-uniform hypergraphs
• On matchings in hypergraphs

This page was built for publication: Matching of given sizes in hypergraphs

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