2020/11/29 by Jun Gao, Hongliang Lu, Gao, Jun +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2011.14363
openalex publication_date 2020/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≥ km, if each of the families F1,…, Fm⊆ [n]\choose k has size more than max\\binomnk - \binomn-m+1k, \binomkm-1k\, then there exist pairwise disjoint subsets e1,…, em such that ei∈ Fi for all i∈ [m]. We prove that there exists an absolute constant n0 such that this rainbow version holds for k=3 and n≥ n0. 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.