Back to Search
Start Over
On the rainbow matching conjecture for 3-uniform hypergraphs
- Source :
- Science China Mathematics. 65:2423-2440
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- Aharoni and Howard, and, independently, Huang, Loh, and Sudakov proposed the following rainbow version of Erd\H{o}s matching conjecture: For positive integers $n,k,m$ with $n\ge km$, if each of the families $F_1,\ldots, F_m\subseteq {[n]\choose k}$ has size more than $\max\{\binom{n}{k} - \binom{n-m+1}{k}, \binom{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\geq 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 {\L}uczak and Mieczkowska and might be of independent interest.<br />Comment: added two references [2,7], accepted for publication in SCIENCE CHINA Mathematics
Details
- ISSN :
- 18691862 and 16747283
- Volume :
- 65
- Database :
- OpenAIRE
- Journal :
- Science China Mathematics
- Accession number :
- edsair.doi.dedup.....b9b613fe46102bad83a6e65e8f79289f