Erdos-Sos猜想及幾個相關的極值組合問題

《Erdos-Sos猜想及幾個相關的極值組合問題》是依託南京大學，由陳耀俊擔任項目負責人的面上項目。

基本介紹

• 中文名：Erdos-Sos猜想及幾個相關的極值組合問題
• 項目類別：面上項目
• 項目負責人：陳耀俊
• 依託單位：南京大學

項目摘要

極值組合是離散數學的最重要分支之一，其主要研究滿足一定條件的一組有限結構(圖，數字，向量等)構成的集合中，最大或最小可能的基數。極值組合問題的研究一方面是數學理論發展的需要，另一方面是實際套用的需要。如 Chudnovsky等人證明的強完美圖定理就是在信息傳輸過程中考慮信道容量時提出的一個著名問題。本項目擬考慮在一定邊數限制以及某些禁用子圖限制條件下各種樹的存在性問題，完全圖的存在性問題，圈的存在性問題，獨立數的最大或最小可能的上下界等等極值組合問題。這些問題既涉及一般圖類，也涉及平面圖等不含某些特殊子圖的圖類。主要研究內容是Erdos-Sos 有關圖的邊數與各種樹存在性之間關係的猜想，以及幾個涉及完全圖、樹、圈、獨立集等存在性且與Erdos-Sos 猜想相關的極值組合問題。Erdos-Sos 猜想目前是極值組合研究的熱點問題之一，與本項目擬考慮的其它幾個問題之間有著某種內在的聯繫。

結題摘要

證明了Erdős-Sós 猜想在圖的獨立數為2或其補圖是平面圖時是正確的；運用結構分析方法，確定了一系列涉及完全圖、圈、輪等圖類平面Ramsey數的準確值；運用結構分析、有限域以及隨機方法確定了一系列涉及圈、星、輪等圖類的Ramsey數準確值；利用最大度建立了稀疏圖鄰點可區分色指標的若干上界；證明了Arkin和Hassin有關頂點劃分猜想在一定條件下是正確的；完全證明了Aouchiche 和Hansen提出的有關圖的平均距離和半徑之間關係的猜想；刻畫了若干給定秩7的圖類以及Z2s+1-連通圖；證明了距離頻譜分配問題是NP-困難的，設計了一個高效的兩階段最佳化算法。