On the rainbow matching conjecture for 3-uniform hypergraphs

Abstract

Aharoni and Howard, and, independently, Huang, Loh, and Sudakov proposed the following rainbow version of Erdős matching conjecture: For positive integers $n,k,m$ with $n\ge km$, if each of the families $F_1,\dots ,F_m\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ has size more than $\max \{(\genfrac{}{}{0ex}{}{n}{k})-(\genfrac{}{}{0ex}{}{n-m+1}{k}),(\genfrac{}{}{0ex}{}{km-1}{k})\}$, then there exist pairwise disjoint subsets $e_1,\dots ,e_m$ such that $e_i\in F_i$ for all $i\in [m]$. We prove that there exists an absolute constant $n_0$ such that this rainbow version holds for $k=3$ and $n\ge n_0$. We convert this rainbow matching problem to a matching problem on a special hypergraph $H$. We then combine several existing techniques on matchings in uniform hypergraphs: find an absorbing matching $M$ in $H$; use a randomization process of Alon et al. to find an almost regular subgraph of $H-V(M)$; and find an almost perfect matching in $H-V(M)$. To complete the process, we also need to prove a new result on matchings in 3-uniform hypergraphs, which can be viewed as a stability version of a result of Łuczak and Mieczkowska and might be of independent interest.

added two references [2,7], accepted for publication in SCIENCE CHINA Mathematics