北理工教授在超图哈密顿圈的研究中取得成果

349e7bf827e94550a8ebd0bc93d7787e.png

日前,北京理工大学数学与统计学院韩杰教授在国际图论与组合数学顶级学术期刊《Journal of Combinatorial Theory, Series B》发表题为“Minimum degree thresholds for Hamilton (k/2)-cycles in k-uniform hypergraphs”的研究论文。该论文决定了对于至少为6的偶数k和至少k/2的d,保证k一致超图中Hamilton (k/2)-圈的存在性的最优d度条件。当n为k的倍数时,此结果加强了ICM2014一小时报告人美国Emory大学杰出教授Rodl,波兰Adam Mickiewicz大学Rucinski教授和美国科学院院士Abel奖得主Rutgers大学杰出教授Szemeredi及英国伯明翰大学教授Treglown,美国佐治亚州立大学教授Zhao等人关于完美匹配的结果。

给定一个图,哈密顿圈是图中过所有顶点的圈。1952年都柏林三一学院教授Dirac证明了图论中最经典的定理之一:对于n至少为3,任意最小度至少n/2的图包含一个哈密顿圈。然而,决定一个图是否有哈密顿圈是著名的NP完全问题。数十年来,图和超图中哈密顿圈存在性的研究一直是图论领域的核心问题。其中,如何将Dirac定理推广到超图中一直是一个自然的重要问题。1999年, 欧洲科学院、匈牙利科学院院士Katona和著名图论专家Kierstead提出了l一致圈(l-uniform cycle)的定义,即要求圈中相邻超边的交的大小固定为l。2011年,Rodl,Rucinski和Szemeredi的突破性进展中决定了3一致超图中保证(k-1)一致圈的最优2度条件 (Adv. Math., 2011)。关于此类问题的数个猜想和后续研究形成了一个图论研究中的一个重要方向。

韩杰与智利圣地亚哥大学的HiepHan教授和美国佐治亚州立大学的YiZhao教授在最新的研究中决定了(k/2)一致圈的最优d度条件,其中d至少为k/2, k至少为6。此结果给出了除(k-1)圈外的第一个k-l整除k的(精确)最优结果,并且是第一个对于d<k-2情况的最优结果 (现有的结果都要求d至少k-2)。另外,当n是k的倍数时,此d度条件恰好是保证k超图包含完美匹配的最优d度条件。由于(k/2)一致圈可以分解成两个依次相交的完美匹配,此研究成果加强了Rodl-Rucinski-Szemeredi和Treglown-Zhao关于完美匹配的结果。

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

论文链接:https://www.sciencedirect.com/science/article/pii/S009589562100099X

附个人简介:

韩杰,教授,北理工数学与统计学院图论与组合优化团队主要成员,图论与组合优化学科方向责任教授。本科毕业于北京理工大学、博士毕业于美国佐治亚州立大学。长期从事图论组合及计算机理论的研究工作,2019年获美国Simons Foundation基金资助,2022年入选工信部启明计划。在Transactions of the American Mathematical Society, International Mathematics Research Notices, Journal of London Mathematical Society等数学权威综合期刊发表论文4篇,图论与组合数学顶级期刊Journalof Combinatorial Theory, Series B发表论文7篇,SODA,ICALP等计算机理论顶级会议发表论文5篇。

以上内容由大学时代综合整理自互联网,实际情况请以官方资料为准。

相关