Matching of given sizes in hypergraphs

DOI10.1137/21M1430327zbMATH Open1498.05217arXiv2106.16068MaRDI QIDQ5043636FDOQ5043636

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

Publication date: 6 October 2022

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

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$.

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

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

zbMATH Keywords

matchingabsorbing methodhypergraph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Title not available (Why is that?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Embedding large subgraphs into dense graphs
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Matchings in 3-uniform hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Fractional and integer matchings in uniform hypergraphs
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• On Perfect Matchings in Uniform Hypergraphs with Large Minimum Vertex Degree
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• A geometric theory for hypergraph matching
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings in 4-uniform hypergraphs
• Title not available (Why is that?)
• The Erdős matching conjecture and concentration inequalities
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Near Perfect Matchings ink-Uniform Hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• Tight co-degree condition for perfect matchings in 4-graphs
• Matchings in hypergraphs of large minimum degree
• Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs
• COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
• Recent advances on Dirac-type problems for hypergraphs
• Perfect Matchings in Hypergraphs and the Erdös Matching Conjecture
• A note on perfect matchings in uniform hypergraphs
• Nearly Perfect Matchings in Uniform Hypergraphs
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II

Cited In (5)

• Matchings in hypergraphs of large minimum degree
• Santa Claus Meets Hypergraph Matchings
• Disjoint perfect matchings in 3‐uniform hypergraphs
• Santa claus meets hypergraph matchings
• Matching orderable and separable 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)