《超圖和隨機超圖的關於哈密頓圈的Dirac類型的問題》是依託福州大學，由陳愛蓮擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：超圖和隨機超圖的關於哈密頓圈的Dirac類型的問題
- 依託單位：福州大學
- 項目類別：青年科學基金項目
- 項目負責人：陳愛蓮
項目摘要,結題摘要,
項目摘要
近十幾年來，隨著電子計算機的普及和積體電路規模的增大，超圖理論及其套用的研究已成為一個新的研究熱點。自1999年Katona和Kierstead給出超圖哈密頓圈的一種新的結構化定義以來，超圖的哈密頓問題，作為超圖理論最基本的也是最具挑戰的問題之一，吸引了很多世界一流圖論和隨機圖論大師的關注。首先受到關注的問題之一就是超圖中是不是也有類似於Dirac定理(一個圖是哈密頓圖的充分條件是該圖的最小度至少是頂點數的一半)的結論。這類問題被稱為Dirac類型的問題。最近，Dirac定理分別被推廣到超圖(2010)和隨機圖(2012)，但總的來說，超圖的Dirac類型的問題的研究還處於初步階段。本項目考慮的是隨機超圖中關於哈密頓圈的Dirac類型的問題和超圖中關於一個d子集的最小度的Dirac類型的問題。目前為止，這兩方面的研究結果幾乎沒有。本項目屬於超圖理論的基礎理論研究，具有一定的理論與套用價值。
結題摘要
研究一個圖性質的穩健性（robustness）是最近幾年的熱門問題之一。其中最為經典的結果就是Dirac‘s 定理：完全圖Kn的每個頂點去掉不超過[n/2]的邊仍然具有哈密頓性質。2012 年Lee 和Sudakov [7]把Dirac 定理推廣到隨機圖，證明了在隨機圖G(n,p)中，如果p＞＞logn/n, 那么幾乎所有G(n,p)的每個最小度不小於（1/2+o(1))np 的子圖都是哈密頓圖。但是，關於隨機超圖的哈密頓Berge圈的Dirac 類型的問題的研究結果幾乎有甚至連閾函式問題都沒有被解決 隨機k 一致超圖Hk (n, p) 中關於哈密頓Berge圈性質的穩健性的問題。本項目的主要研究內容就是研究隨機超圖的哈密頓Berge圈的Dirac 類型的問題。目前，（一）我們已經將上面的兩個經典結果推廣到隨機超圖的哈密頓Berge圈性質上：在隨機k一致超圖H_k(n,p)中，如果p＞＞logn/n^{k-1}, 那么幾乎所有H_k(n,p)的每個最小度不小於（1/2^{k-1}+o(1)){n-1\choose k}p 的子圖都有一個哈密頓Berge圈，並且兩個界在某種程度上都是最好的。我們的結果順便也解決了隨機k一致超圖 的閾函式問題：logn/n^{k-1} 是H_k(n,p) 的Hamiltonian Berge cycle性質的閾函式。另外，我們還將上面的結論中的度條件推廣到不相容系統，也得到了相應的結果，其中的兩個界在某種程度上也是最好的。Berge cycle 是最早最經典的一種超圖圈定義，但是由於其結構比較複雜，研究難度比較大。關於現代圖論關於Berge cycle的研究較少。我們的結果解決了隨機k一致超圖 的Hamiltonian Berge cycle 理論中比較關鍵的兩個問題，這對於該理論的進一步發展有著破凍的作用，和比較重要的理論套用價值。
