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