北理工教授在超圖哈密頓圈的研究中取得成果
發布日期：2022-09-14 供稿：數學與統計學院
編輯：王歡 審核：陳珂 閱讀次數：
日前，北京理工大學數學與統計學院韓杰教授在國際圖論與組合數學頂級學術期刊《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基金資助。在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篇。
分享到：