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 s...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.展开更多
Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G...Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G has a rainbow matching of size 6, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18： #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition （X, Y） and max{lXl, IYI} 〉 （σ2 ＋ 4σ - 4）/4, then G has a rainbow matching of size σ.展开更多
基金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)+1 种基金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.
文摘Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G has a rainbow matching of size 6, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18： #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition （X, Y） and max{lXl, IYI} 〉 （σ2 ＋ 4σ - 4）/4, then G has a rainbow matching of size σ.
