科研成果

北理工教师在图因子研究中取得成果


日前,北京理工大学金沙js9线路中心主页韩杰教授在国际权威期刊《Journal of Combinatorial Theory, Series B》连续发表题为“Tiling multipartite hypergraphs in Quasi-random Hypergraphs”和“Embedding clique-factors in graphs with low l-independence number”的两篇研究论文。此两篇论文研究了具有一定随机性的图与超图中 F 因子的存在性问题,给出了渐近最优的度条件和密度条件。

给定一个图G,一个F因子是指多个顶点不交的F覆盖G的所有顶点。当 F 为一条边的时候,F因子也被成为完美匹配。著名的Hajnal-Szemerédi定理给出了图中保证团因子的最优度条件。除了完美匹配情况以外,决定一个图是否F因子是著名的NP完全问题。数十年来,图和超图中F因子的存在性的研究一直是图论领域的核心问题。此问题在经典稠密图中与经典随机图中都有较完整的结果。近年来,关于此问题的研究主要集中在考虑具有一定(但较弱)随机性的图与超图。其中一个研究方向是考虑图的独立数为次线性的情况(不存在线性大小的独立集),另一个为考虑随机性很弱的拟随机超图。

韩杰与山东大学的王光辉教授团队和韩国科学技术院大学的Jaehoon Kim教授在最新的研究中决定了独立数次线性图中团因子存在性的最优度条件,并否定了前人提出的猜想。在另一研究中,韩杰与华中师范大学教师丁来浩、山东大学王光辉教授团队研究了拟随机超图中退化F因子存在性的最优密度问题并得到了一系列成果。其中关于3一致超图中因子问题得到的密度(上)界匹配了著名数学家Mubayi于2016年得到的下界。

这两项研究工作中作者按字母序排列,韩杰教授均为通讯作者。

论文链接

https://www.sciencedirect.com/science/article/pii/S0095895622001277

https://www.sciencedirect.com/science/article/pii/S009589562300014X

附研究团队和个人简介:

韩杰,教授,北理工金沙js9线路中心主页图论组合团队主要成员,图论与组合优化学科专业责任教授。本科毕业于北京理工大学、博士毕业于美国佐治亚州立大学。长期从事图论组合及计算机理论的研究工作,2019年获美国Simons Foundation基金资助,2022年入选国家高层次青年人才计划。在Transactions of the American Mathematical Society, International Mathematics Research Notices, Journal of London Mathematical Society等数学综合权威期刊发表学术论文4篇,图论领域顶级杂志Journal of Combinatorial Theory, Series B上发表论文9篇,SODA,ICALP等计算机理论顶级会议发表论文5篇。