A better bound on the size of rainbow matchings

Abstract

Aharoni and Howard conjectured that, for positive integers $n,k,t$ with $n\ge k$ and $n\ge t$, if $F_1,\dots ,F_t\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ such that $|F_i|>\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-t+1}{k}\right)$ for $i\in [t]$ then there exist $e_i\in F_i$ for $i\in [t]$ such that $e_1,\dots ,e_t$ are pairwise disjoint. Huang, Loh, and Sudakov proved this conjecture for $t<n/(3k^2)$. In this paper, we show that this conjecture holds for $t\le n/(2k)$ and $n$ sufficiently large.

References in corpus (1)

• Near perfect matchings in uniform hypergraphs

Cited by in corpus (6)

• Rainbow version of the Erd\H os Matching Conjecture via Concentration
• Rainbow spanning structures in graph and hypergraph systems
• Rainbow perfect matchings for 4-uniform hypergraphs
• Extremal Problem for Matchings and Rainbow Matchings on Direct Products
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
• Transversal Hamilton cycle in hypergraph systems