北理工教授在超圖哈密頓圈的研究中取得成果
發(fā)布日期：2022-09-14 供稿：數(shù)學與統(tǒng)計學院
編輯：王歡 審核：陳珂 閱讀次數(shù)：
日前,，北京理工大學數(shù)學與統(tǒng)計學院韓杰教授在國際圖論與組合數(shù)學頂級學術期刊《Journal of Combinatorial Theory, Series B》發(fā)表題為“Minimum degree thresholds for Hamilton (k/2)-cycles in k-uniform hypergraphs”的研究論文。該論文決定了對于至少為6的偶數(shù)k和至少k/2的d,，保證k一致超圖中Hamilton (k/2)-圈的存在性的最優(yōu)d度條件,。當n為k的倍數(shù)時，此結果加強了ICM2014一小時報告人美國Emory大學杰出教授Rodl,，波蘭Adam Mickiewicz大學Rucinski教授和美國科學院院士Abel獎得主Rutgers大學杰出教授Szemeredi及英國伯明翰大學教授Treglown,，美國佐治亞州立大學教授Zhao等人關于完美匹配的結果。
給定一個圖,，哈密頓圈是圖中過所有頂點的圈,。1952年都柏林三一學院教授Dirac證明了圖論中最經典的定理之一：對于n至少為3，任意最小度至少n/2的圖包含一個哈密頓圈,。然而,，決定一個圖是否有哈密頓圈是著名的NP完全問題。數(shù)十年來,，圖和超圖中哈密頓圈存在性的研究一直是圖論領域的核心問題,。其中，如何將Dirac定理推廣到超圖中一直是一個自然的重要問題,。1999年,， 歐洲科學院、匈牙利科學院院士Katona和著名圖論專家Kierstead提出了l一致圈（l-uniform cycle）的定義,，即要求圈中相鄰超邊的交的大小固定為l,。2011年，Rodl,，Rucinski和Szemeredi的突破性進展中決定了3一致超圖中保證(k-1)一致圈的最優(yōu)2度條件 (Adv. Math., 2011),。關于此類問題的數(shù)個猜想和后續(xù)研究形成了一個圖論研究中的一個重要方向。
韓杰與智利圣地亞哥大學的HiepHan教授和美國佐治亞州立大學的YiZhao教授在最新的研究中決定了(k/2)一致圈的最優(yōu)d度條件,，其中d至少為k/2, k至少為6,。此結果給出了除(k-1)圈外的第一個k-l整除k的（精確）最優(yōu)結果，并且是第一個對于d<k-2情況的最優(yōu)結果 (現(xiàn)有的結果都要求d至少k-2),。另外,，當n是k的倍數(shù)時，此d度條件恰好是保證k超圖包含完美匹配的最優(yōu)d度條件,。由于(k/2)一致圈可以分解成兩個依次相交的完美匹配,，此研究成果加強了Rodl-Rucinski-Szemeredi和Treglown-Zhao關于完美匹配的結果。
這項研究工作中三位作者按字母序排列,，韓杰教授為通訊作者,。
論文鏈接：https://www.sciencedirect.com/science/article/pii/S009589562100099X
附個人簡介：
韓杰，教授，北理工數(shù)學與統(tǒng)計學院圖論與組合優(yōu)化團隊主要成員,，圖論與組合優(yōu)化學科方向責任教授,。本科畢業(yè)于北京理工大學、博士畢業(yè)于美國佐治亞州立大學,。長期從事圖論組合及計算機理論的研究工作,，2019年獲美國Simons Foundation基金資助。在Transactions of the American Mathematical Society, International Mathematics Research Notices, Journal of London Mathematical Society等數(shù)學權威綜合期刊發(fā)表論文4篇,，圖論與組合數(shù)學頂級期刊Journalof Combinatorial Theory, Series B發(fā)表論文7篇,，SODA，ICALP等計算機理論頂級會議發(fā)表論文5篇,。
分享到：