Rainbow perfect matchings for 4-uniform hypergraphs

DOI10.1137/21M1442383MaRDI QIDQ5093585zbMATH OpenOpenAlexFDO

Authors Hongliang Lu, Yan Wang, Xingxing Yu

Publication date 28 July 2022

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

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

zbMATH Keywords

absorbing methodhypergraphperfect matchingrainbow matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $n$ be a sufficiently large integer with $nequiv0pmod4$ and let $F_{i}subseteq[n]choose4$ where $iin[n/4]$. We show that if each vertex of $F_i$ is contained in more than $n-1choose3-3n/4choose3$ edges, then $F_1,ldots,F_{n/4}$ admits a rainbow matching, i.e., a set of $n/4$ edges consisting of one edge from each $F_i$. This generalizes a deep result of Khan on perfect matchings in 4-uniform hypergraphs.

Recommendations

• Rainbow matchings for 3-uniform hypergraphs
• Perfect matchings in 4-uniform hypergraphs
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
• Rainbow matchings in properly-colored hypergraphs
• Rainbow fractional matchings

Cites work

• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• A new generalization of the Erdős-Ko-Rado theorem
• A rainbow \(r\)-partite version of the Erdős-Ko-Rado theorem
• Asymptotic behavior of the chromatic index for hypergraphs
• Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Hypergraph containers
• Improved bounds for Erdős' matching conjecture
• Independent sets in hypergraphs
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Matchings in 3-uniform hypergraphs
• Near perfect coverings in graphs and hypergraphs
• Near-perfect clique-factors in sparse pseudorandom graphs
• Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
• On Erdős' extremal problem on matchings in hypergraphs
• On a rainbow version of Dirac's theorem
• On matchings in hypergraphs
• On perfect matchings in \(k\)-complexes
• On the maximum number of edges in a hypergraph with given matching number
• On the rainbow matching conjecture for 3-uniform hypergraphs
• On the size of graphs with complete-factors
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Perfect matchings in 4-uniform hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• Rainbow matchings for 3-uniform hypergraphs
• Rainbow matchings in \(k\)-partite hypergraphs
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Reducibility among combinatorial problems
• Simple juntas for shifted families
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• The probabilistic method
• The size of a hypergraph and its matching number

Cited in

(6)

• Rainbow matchings for 3-uniform hypergraphs
• Rainbow spanning structures in graph and hypergraph systems
• Transversal Hamilton cycle in hypergraph systems
• Perfect matchings in 4-uniform hypergraphs
• A general approach to transversal versions of Dirac‐type theorems
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs

This page was built for publication: Rainbow perfect matchings for 4-uniform hypergraphs

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