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