本文選題：圖拉格朗日 + 左壓縮��； 參考：《湖南大學(xué)》2016年博士論文

【摘要】：在組合數(shù)學(xué)史上,有一段豐富的研究歷史是關(guān)于超圖的圖拉格朗日及其應(yīng)用的。1941年,Turan回答了下面的問題：一個(gè)有n個(gè)頂點(diǎn)的圖,它不包含階為t(t給定)的完全子圖的最大邊數(shù)是多少?這就是著名的Turan定理。1965年,Motzkin和Straus在一個(gè)圖的圖拉格朗日和其最大團(tuán)的階之間建立了一個(gè)顯著的聯(lián)系。它也提供了一個(gè)新的證明Turan定理的方法。這個(gè)新的證明方法激起了對(duì)r一致超圖的圖拉格朗日的研究興趣。在很多應(yīng)用中,需要用到超圖的圖拉格朗日的一個(gè)上限。在估計(jì)一些超圖的Turan密度的過程中,Frankl和Furedi提出了下面的問題：給定r≥3,m∈N,一個(gè)有m條邊的r圖的圖拉格朗日最大能有多大?他們猜想在所有的有m條邊的r圖中,Gr,m(由N的r子集的集合的colex序中的前m個(gè)集合所形成的m條邊的r圖)有最大的圖拉格朗日,也就是說,r一致超圖G的圖拉格朗日小于等于Gr,m的圖拉格朗日。本文證明了Frankl和Furedi的猜想在某些條件下成立。Moztkin和Straus的結(jié)果暗含著以上猜想對(duì)于r=2是對(duì)的。對(duì)于r≥3,這個(gè)猜想非常具有挑戰(zhàn)性。Talbot首先在某些情況下證實(shí)了這個(gè)猜想。隨后,Peng, Zhao, Tang等在更多的情況下證實(shí)了這個(gè)猜想。Motzkin和Straus的結(jié)果不能直接推廣到r一致超圖,所以Peng和Zhao試圖探索當(dāng)邊數(shù)在一定范圍內(nèi),一個(gè)超圖的圖拉格朗日和超圖的最大團(tuán)數(shù)之間的關(guān)系,并提出了與之相關(guān)的兩個(gè)猜想。這兩個(gè)猜想細(xì)化了當(dāng)邊數(shù)在這個(gè)范圍內(nèi)的Frankl-Fiiredi猜想。他們還證明了猜想中的一個(gè)關(guān)于3一致超圖的,即當(dāng)邊數(shù)在某個(gè)范圍內(nèi)時(shí),3一致超圖的圖拉格朗日是它的最大團(tuán)的圖拉格朗日。本文證明了當(dāng)邊數(shù)在那個(gè)范圍內(nèi)時(shí),如果一個(gè)3一致超圖不包含這樣的階的一個(gè)團(tuán),那么在某些條件下,這個(gè)3一致超圖的圖拉格朗日嚴(yán)格地小于這樣的階的一個(gè)完全3一致超圖的圖拉格朗日。這也為以上猜測(cè)提供了一些依據(jù)�；谝延械慕Y(jié)果,本文繼續(xù)對(duì)3一致超圖G的圖拉格朗日與G3,m的圖拉格朗日之間的關(guān)系進(jìn)行研究。由于直接得出它們之間的聯(lián)系比較困難,所以附加了一些條件,如在滿足G的邊與G3,m的邊的對(duì)稱差的個(gè)數(shù)小于等于某個(gè)具體數(shù)值的情況下,或者在滿足邊數(shù)等于某個(gè)與t有關(guān)的式子的情況下,來探討它們之間的聯(lián)系。在滿足左壓縮的前提下,靈活替換,證明出了3一致超圖的圖拉格朗日小于等于G3,m的圖拉格朗日,改進(jìn)了研究結(jié)果。接著研究了在一些條件下,3一致超圖的圖拉格朗日和最大團(tuán)之間的關(guān)系。本文是在m在某個(gè)范圍內(nèi),G不包含t-1階團(tuán),且同時(shí)包含頂點(diǎn)t-1和t的邊數(shù)不大于某個(gè)具體數(shù)值的情況下研究的。通過運(yùn)用迭代法和替換法,得出了G的圖拉格朗日嚴(yán)格地小于t-1階的完全3圖的圖拉格朗日。本文繼續(xù)探索了3一致超圖的圖拉格朗日和最大團(tuán)之間的關(guān)系。在研究的過程中加入了一些條件,如從t-1階的團(tuán)中移去了指定的p條邊,t大于等于一p的多項(xiàng)式,獲得了G的圖拉格朗日嚴(yán)格地小于t-1階的完全3圖的圖拉格朗日。這里由于p的任意性,所以結(jié)論有較好的一般性,以及較廣的覆蓋面�；谝延械难芯砍晒�,只要證明了左壓縮3一致超圖,也就證明了3一致超圖。這大大降低了計(jì)算復(fù)雜度。在此基礎(chǔ)上,令G是在頂點(diǎn)集[t]上有m條邊的一個(gè)左壓縮3圖,如果從t-1階的團(tuán)中移去p條邊,t大于等于p的一個(gè)一次多項(xiàng)式,那么G的圖拉格朗日嚴(yán)格地小于t-1階的完全3圖的圖拉格朗日。這在計(jì)算復(fù)雜度和一般性上改進(jìn)了以往的研究結(jié)果,并且部分地驗(yàn)證了Peng-Zhao提出的猜想�？傊�,通過對(duì)具體情況的研究,起初的目的是證明Frankl-Furedi猜想。但是目前的方法有一定的局限性。由于有很多種情況,每種情況的替換方法又不一樣,所以總結(jié)出來比較困難。然而,如果可以克服一些困難,那么本文的方法可能得到推廣,Frankl-Furedi猜想也許能夠得到證明。本文為Frankl-Furedi猜想提供了更多的依據(jù)。
[Abstract]:In the history of combinatorial mathematics, there is a rich history of research history on Hypergraph Lagrange and its application.1941 years. Turan answered the following question: a graph with n vertices, which does not contain the maximum number of complete subgraphs of the order t (t given)? This is the famous Turan theorem.1965, Motzkin and Straus in one Graph Lagrange has a significant relationship with the order of its largest group. It also provides a new method to prove the Turan theorem. This new proof method arouses the interest in the study of graph Lagrange of the uniform hypergraph of R. In many applications, we need to use a upper limit of graph Lagrange of hypergraph. In the process of Turan density of some hypergraphs, Frankl and Furedi put forward the following questions: how big is the maximum of a graph of a R diagram with a given r equal to 3, m N, a r graph with a m edge? They conjecture that in all r diagrams with m edges, Gr, M. Figure Lagrange, that is to say, R unanimous hypergraph G's graph Lagrange is less than equal to Gr, M's graph Lagrange. This paper proves that the conjecture that Frankl and Furedi conjectures of.Moztkin and Straus under certain conditions implies that the above conjecture is right for r=2. For R > 3, this guess is very challenging first in some cases. Then, this conjecture is confirmed. Then, Peng, Zhao, Tang and so on in more cases confirm that the conjecture that the results of.Motzkin and Straus can not be extended directly to the R uniform hypergraph, so Peng and Zhao try to explore the relationship between the graph Lagrange and the maximum number of hypergraphs of a hypergraph in a certain range. The two conjectures. The two conjectures refine the Frankl-Fiiredi conjecture that the number of sides are in this range. They also prove that one of the conjectures on the 3 uniform hypergraph, that is, when the number of sides is in a certain range, the graph Lagrange of the 3 unanimous hypergraph is its largest group of Tulag Lang days. This paper proves that the number of sides is in that range. If a 3 uniform hypergraph does not contain a regiment of such a order, in some conditions, the graph Lagrange of the 3 uniform hypergraph is strictly less than a graph Lagrange of a fully 3 uniform hypergraph of the order of this order. This provides some basis for the above guess. Based on the existing results, this article continues to the 3 uniform hypergraph G. The relationship between graph Lagrange and G3, M's graph Lagrange is studied. As it is difficult to get a direct connection between them, some conditions are added, such as if the number of symmetric differences between the edges of G and G3, M is less than a specific value, or the number of sides equal to a t related formula. The relationship between them is discussed. Under the premise of satisfying the left compression, a flexible replacement is given to prove that the graph Lagrange of 3 uniform hypergraph is less than G3 or equal to that of M, and the results of the study are improved. Then, the relationship between the graph Lagrangian day and the maximum group of 3 uniform hypergraphs is studied under some conditions. This article is in a certain M In a range, G does not contain T-1 orders, and the number of vertices T-1 and t is not more than a certain number. By using the iterative method and replacement method, the graph Lagrange of G is strictly less than the complete 3 graph of the T-1 order. This paper continues to explore the 3 consistent hypergraph of graph Lagrange and the largest group. The relationship between them. In the course of the study, some conditions are added, such as removing the specified P edge from the T-1 order group, t greater than the polynomial of a P, and obtaining graph Lagrange of G's graph Lagrange strictly less than the complete 3 graph of the T-1 order. Here, the conclusion has better generality and wider coverage because of the arbitrariness of P. Surface. Based on the existing research results, as long as the left compression 3 uniform hypergraph is proved, the 3 uniform hypergraph is proved. This greatly reduces the computational complexity. On this basis, G is a left compression 3 graph with m edges on the vertex set [t]. If the P edge is removed from the T-1 order group, t is greater than a single polynomial of P, then the graph of G Lagrange is strictly less than the graph Lagrange of the complete 3 graph of the T-1 order. This improves the previous research results in computational complexity and generality, and partly verifies the conjecture proposed by Peng-Zhao. In a word, the original purpose is to prove the Frankl-Furedi conjecture through the study of the specific circumstances. But the present method has a certain situation. Limited. Because there are many cases, the substitution method of each case is different, so it is difficult to sum up. However, if some difficulties can be overcome, the method of this paper may be popularized, and the Frankl-Furedi conjecture may be proved. This article provides more basis for the Frankl-Furedi conjecture.

【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 林啟忠,房杰,劉娟,杜智華;兩類特殊超圖的分?jǐn)?shù)橫貫[J];新疆師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年03期

2 唐宇軒;;圈區(qū)間超圖相關(guān)性質(zhì)的討論[J];新疆師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

3 劉木伙;柳柏濂;;嚴(yán)格(d)-連通無圈超圖的計(jì)數(shù)[J];數(shù)學(xué)學(xué)報(bào);2007年06期

4 范新愛;趙守娟;;r一致導(dǎo)出匹配可擴(kuò)張超圖及性質(zhì)[J];新鄉(xiāng)學(xué)院學(xué)報(bào)(自然科學(xué)版);2009年05期

5 石怡;王福;;有關(guān)交簇超圖的兩個(gè)結(jié)論[J];兵團(tuán)教育學(xué)院學(xué)報(bào);2009年05期

6 朱俊杰;;超圖的奇圈橫貫[J];成都大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年02期

7 孫林;;完美圖在超圖上的推廣[J];新疆師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年01期

8 王福;石怡;杜智華;;一類超圖的橫貫[J];石河子大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

9 趙凌琪;馮偉;徐春雷;吉日木圖;;無圈超圖規(guī)模的進(jìn)一步研究[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2012年05期

10 毛經(jīng)中;;關(guān)于超圖中的樹——超樹[J];華中師院學(xué)報(bào)(自然科學(xué)版);1982年S1期

相關(guān)重要報(bào)紙文章 前10條

1 本報(bào)駐東京記者 吳仲國(guó);中國(guó)軟件在日本叫響知名品牌成市場(chǎng)寵兒[N];科技日?qǐng)?bào);2002年

2 證券時(shí)報(bào)記者 吳中珞;超圖軟件信披創(chuàng)新 微博釋疑股吧發(fā)帖詳解年報(bào)延期[N];證券時(shí)報(bào);2011年

3 本報(bào)記者 朱熹妍;地理信息火爆 超圖地理專注成器[N];經(jīng)濟(jì)觀察報(bào);2008年

4 記者 趙一蕙;超圖軟件業(yè)績(jī)快報(bào)“失準(zhǔn)”逾20%[N];上海證券報(bào);2013年

5 欒玲　趙培;超圖軟件：中國(guó)“智”造的跨國(guó)軟件企業(yè)[N];中國(guó)高新技術(shù)產(chǎn)業(yè)導(dǎo)報(bào);2010年

6 本報(bào)記者 解佳濤　戈清平;超圖軟件：做“中國(guó)智造”的跨國(guó)軟件企業(yè)[N];中國(guó)高新技術(shù)產(chǎn)業(yè)導(dǎo)報(bào);2010年

7 本報(bào)記者 梁爽;超圖：十年打造地理信息超級(jí)版圖[N];中國(guó)政府采購(gòu)報(bào);2012年

8 徐洋;北京市委書記郭金龍視察超圖軟件公司[N];中國(guó)測(cè)繪報(bào);2012年

9 本報(bào)記者 鄭燃;超圖軟件：讓應(yīng)急事件避免盲人摸象[N];政府采購(gòu)信息報(bào);2011年

10 江雪;鐘耳順鐘情GIS[N];中國(guó)企業(yè)報(bào);2007年

相關(guān)博士學(xué)位論文 前10條

1 古萬榮;基于超圖模型的新聞推薦研究[D];華南理工大學(xué);2015年

2 孫艷萍;3一致超圖的拉格朗日和最大團(tuán)之間的關(guān)系的研究[D];湖南大學(xué);2016年

3 彭豪;超圖的Motzkin-Straus型結(jié)果及Frankl-F(?)redi猜想[D];湖南大學(xué);2015年

4 吳艷;3-一致超圖分解及相關(guān)問題[D];北京交通大學(xué);2010年

5 吳穎敏;市場(chǎng)機(jī)遇發(fā)現(xiàn)的超圖支持方法研究[D];華中科技大學(xué);2009年

6 葉淼林;圖與超圖理論中的譜方法[D];安徽大學(xué);2010年

7 吉日木圖;圖的標(biāo)號(hào)及超圖分解問題研究[D];大連理工大學(xué);2006年

8 王琦;網(wǎng)絡(luò)中的超圖嵌入問題[D];山東大學(xué);2007年

9 蔡p，

本文編號(hào)：1878796