Rainbow perfect matchings for 4-uniform hypergraphs

DOI10.1137/21M1442383zbMATH Open1493.05218arXiv2105.08608OpenAlexW4296917346MaRDI QIDQ5093585FDOQ5093585

Authors: Hongliang Lu, Yan Wang, Xingxing Yu 

Publication date: 28 July 2022

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

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.

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

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

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)

Cites Work

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

Cited In (6)

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

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)