《圖Ramsey數及編碼理論中相關的極值問題》是依託南京大學，由陳耀俊擔任項目負責人的面上項目。
基本介紹
- 中文名：圖Ramsey數及編碼理論中相關的極值問題
- 項目類別：面上項目
- 項目負責人：陳耀俊
- 依託單位：南京大學
項目摘要,結題摘要,
項目摘要
圖Ramsey 理論研究系統規模的一種臨界狀態，即一個大的系統究竟要大到什麼程度才會包含某個給定的子系統。編碼理論是信息和理論計算機科學研究的核心內容之一，主要研究如何編碼才能使一個信道信息傳輸量達到或接近其理論上的極大值，即Shannon容量。基於圖的編碼方法稱之為現代編碼理論。與基於有限域的經典編碼理論相比，該方法更容易逼近某些信道的Shannon容量。本項目主要利用圖論的方法研究一個信道的Shannon容量、當G 和H 是一些特殊圖類時圖Ramsey數R(G,H) 的值及其上下界，R(G,H) 與Shannon容量之間的關係，圖的其他參數如獨立數、色數、譜半徑等與Shannon容量之間的關係，以及與之相關的一些組合結構與算法。這些研究可以推動圖Ramsey理論的發展，為基於圖的編碼最佳化設計提供理論基礎。
結題摘要
在本項目中，首次利用圖的邊數與圍長之間的關係, 圖的邊數與泛圈性之間的關係以及一個圖與其補圖圍長之間的關係，完全證明了Surahmat 等人關於大圈對偶階數輪的猜想，基本上解決了Surahmat 等人關於大圈對奇階數輪的猜想，為這一類問題的研究提供了全新的思路。基於此種方法，本項目還確定了其他幾類圈-輪型Ramsey數的值。證明了輪-四圈Ramsey函式與另一個備受關注的困難問題星-四圈Ramsey函式是相等的。在平面圖方面，確定了不含四圈平面圖最大可能邊數並考慮了相應的極值結構，計算了幾乎所有的圈-輪平面Ramsey數以及完全圖-樹平面Ramsey數，後者是與通常Ramsey數經典結果Chvátal定理相應的平面Ramsey數形式；證實了Sun等人有關四圈-完全圖猜想的一個特例；證明了當圖的補圖是平面圖時，Erdös-Sós有關圖的邊數與各階樹存在性之間關係的著名猜想是成立的。研究了按照譜半徑對樹的排序問題，確定了第8-10棵具有最小譜半徑的樹。給出了賦權圖的譜半徑和拉普拉斯譜半徑的若干下界，並刻畫了達到下界的圖的結構。藉助圖的鄰接矩陣譜半徑，分別給出了一個二部圖具有Hamilton圈和一般圖具有Hamilton路的新的充分條件。利用圖的結構性質，結合代數方法，分別給出了一個圖是k-邊連通的拉普拉斯譜條件和無符號拉普拉斯譜條件，也分別得到了與圖的圍長有關的拉普拉斯譜條件，推廣了一些已知結論。另外，本項目還研究Burnt Pancake圖的條件邊容錯哈密爾頓性，證明了該圖類是(2n-5)-條件邊容錯哈密爾頓圖。
