On the rainbow matching conjecture for 3-uniform hypergraphs  被引量:1

在线阅读下载全文

作  者: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[理学—数学]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象