圖與隨機圖的漸近與極值性質

《圖與隨機圖的漸近與極值性質》是依託中國科學技術大學，由沈嘉擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖與隨機圖的漸近與極值性質
• 項目類別：青年科學基金項目
• 項目負責人：沈嘉
• 依託單位：中國科學技術大學

中文摘要

本研究項目將主要研究離散的數學對象中有關圖、隨機圖等組合結構上的漸近性質。圖與隨機圖的漸近性質方面的研究與數學中多個分支都有密切關聯，並且在理論計算機科學特別是大規模網路 (比如internet) 的基礎理論等方面具有重要意義。本項目的主要研究內容包括圖與隨機圖的F-free 子圖的性質，以及最近新出現的更廣泛意義下的隨機子圖的若干漸近與極值性質。在這一廣義模型下，母圖G可以為任意偽隨機圖，並且母圖G中邊的稀疏稠密程度可由參數d 控制。這種廣義的隨機子圖是經典的隨機圖模型的自然推廣。. 本項目中考慮的問題為原有經典問題的具有一般性的總體推廣，是具有基本意義的新的理論問題。在本研究中所採取的方法主要為超圖方法，結構分解的技巧以及機率方法以及其他方法等，其中很多為近年來圖論與組合中新發展出來的新的理論與工具。本項目將通過對這些內容的研究，力爭在理論和方法上取得較大突破，實現擬定的目標。

結題摘要

本研究項目將主要研究離散的數學對象中有關圖、隨機圖等組合結構上的漸近性質。圖與隨機圖的漸近性質方面的研究與數學中多個分支都有密切關聯，並且在理論計算機科學特別是大規模網路 (比如internet) 的基礎理論等方面具有重要意義。本項目的主要研究內容包括圖與隨機圖的F-free 子圖的性質，以及最近新出現的更廣泛意義下的隨機子圖的若干漸近與極值性質。在這一廣義模型下，母圖G可以為任意偽隨機圖，並且母圖G中邊的稀疏稠密程度可由參數d 控制。這種廣義的隨機子圖是 經典的隨機圖模型的自然推廣。本項目中考慮的問題為原有經典問題的具有一般性的總體推廣，是具有基本意義的新的理論問題。在本研究中所採取的方法主要為超圖方法，結構分解的技巧以及機率方法以及其他方法等，其中很多為近年來圖論與組合中新發展出來的新的理論與工具。本項目將通過對這些內容的研究，力爭在 理論和方法上取得較大突破，實現擬定的目標。 本項目已完成論文4篇，其中一篇已發表在SCI收錄雜誌，有兩篇在投稿，還有一篇待投稿。另外，本項目的研究結果預期會再產生2-3篇論文，正在整理寫作中。 本項目執行過程中，不但在理論上取得了若干結果，而且其中一些理論結果預期會有實際的套用。