《圖分割和標誌代數》是依託中國科學技術大學，由馬傑擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖分割和標誌代數
- 項目類別：青年科學基金項目
- 項目負責人：馬傑
- 依託單位：中國科學技術大學
中文摘要,結題摘要,
中文摘要
圖分割問題，在極值組合、最佳化和計算機科學等領域中有廣泛的套用和重要的影響。標誌代數，作為近年來蓬勃發展的一門新興理論，對組合特別是極值組合的發展有著巨大的推動力。申請者已經在包括這兩大領域在內的一些推動學科發展的重要問題上，得到了不少重大創新成果。本項目主要圍繞著圖分割和標誌代數這兩大主題開展研究。其研究內容包括：圖分割範數問題，關於平分劃分的Bollobas-Scott猜想，Caccetta-Haggkvist猜想，歐拉有向圖的Seymour-Jackson猜想以及無三角形圖的Erdos猜想。
結題摘要
本項目主要研究了關於圖的分割問題，標識代數等圖論中的重要問題，通過研究我們取得了一系列結果，包括：我們證明了Bollobas and Scott提出的關於圖平分劃分的猜想，進一步我們還證明了這個猜想對任意k-劃分都是正確的；證明了Scott關於圖分割的範數問題；證明了關於Turan數和染色推廣Turan數之間關係的Keevash-Sudakov猜想對一個無窮圖集成立，得到了這個猜想目前最好的結果，並且還得到了當這個猜想成立時對應的染色是唯一的；推廣了眾所周知的完全二部圖的Turan數的結果到完全r部r一致超圖，提供了一種利用隨機代數的方法構造非退化的特殊的圖（超圖）來解決一系列Turan類問題的想法；證明了關於Thomassen在1983年提出的關於最小頂點度較大的圖中的圈長的猜想當k是偶數時，猜想成立，當k是奇數且將最小頂點度滿足的條件改為“大於等於k+4”時猜想成立；關於Verstraete的關於超圖的圈長問題，發展了一種新的方法來研究超圖中的圈長問題，證明了每個平均頂點度大於等於7r(k + 1)的r-一致線性超圖都包含k條連續長度的Berge圈；證明了對最小度k和最長圈長度c滿足條件10 ≤ c < n且e(G) > max{f(n, k +1, c), f(n, ⌊2c⌋ - 1, c)}的n的頂點的二連通圖的Turan類問題的結果進行了最佳化，並且得到了一個穩定性的結論。 除上述主要結果外，我們還得到了包括圖染色在內的其他結果。在本項目的支持下，一共在國際組合數學頂級期刊Combinatorica，JCTB，JCTA等數學期刊上發表學術論文11篇。
