On the rainbow matching conjecture for 3-uniform hypergraphs  

作　　者：Jun Gao Hongliang Lu Jie Ma Xingxing Yu 

机构地区：[1]School of Mathematical Sciences,University of Science and Technology of China,Hefei 230026,China [2]School of Mathematics and Statistics,Xi’an Jiaotong University,Xi’an 710049,China [3]School of Mathematics,Georgia Institute of Technology,Atlanta,GA 30332,USA

出　　处：《Science China Mathematics》2022年第11期2423-2440,共18页中国科学：数学（英文版）

基　　金：supported by the National Key R and D Program of China(Grant No.2020YFA0713100);National Natural Science Foundation of China(Grant Nos.11871391,11622110 and 12125106);Fundamental Research Funds for the Central Universities,Anhui Initiative in Quantum Information Technologies(Grant No.AHY150200);National Science Foundation of USA(Grant No.DMS-1954134).

摘　　要：Aharoni and Howard and,independently,Huang et al.(2012)proposed the following rainbow version of the Erd os matching conjecture:For positive integers n,k and m with n≥km,if each of the families F1,……,Fm⊆([n]k)has size more than max{(n k)−(n-m+1 k);(km-1 k)},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≥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.(2012)to find an almost regular subgraph of H−V(M);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 Luczak and Mieczkowska(2014)and might be of independent interest.

关 键 词：rainbow matching conjecture ERD 

分 类 号：O157.5[理学—数学]