Back to Search Start Over

On the rainbow matching conjecture for 3-uniform hypergraphs

Authors :
Jie Ma
Hongliang Lu
Xingxing Yu
Jun Gao
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