關(guān)于圖size Ramsey數(shù)若干問題的研究.pdf

1、圖論是一門年輕而又發(fā)展極為迅速的學(xué)科,現(xiàn)代圖論最顯著的特征是許多現(xiàn)代方法的出現(xiàn),如代數(shù)、幾何、概率、分析方法等。圖的Ramsey理論作為圖論的一個極具吸引力的研究分支,同時也是組合數(shù)學(xué)中一個龐大而豐富的領(lǐng)域,它起源于1930年英國數(shù)學(xué)家Frank Ramsey的文章《On a Problem of FormalLogic》[73]。在這篇文章里Frank Ramsey討論了在某種條件下無論對集合如何劃分都能夠產(chǎn)生人們預(yù)期想要得到的子集的

2、現(xiàn)象。后來人們在他工作的基礎(chǔ)上不斷擴(kuò)充,確定了Ramsey理論的研究內(nèi)容為:在某種條件下,無論對一個大系統(tǒng)(結(jié)構(gòu))如何進(jìn)行分割,總是能夠得到人們預(yù)期想要得到的子系統(tǒng)(結(jié)構(gòu)),這種大系統(tǒng)的最小階便稱之為Ramsey數(shù)。這里的系統(tǒng)即由相互關(guān)聯(lián)的事物所組成,要研究這種系統(tǒng)可以通過很多種方式進(jìn)行探討,其中“圖”是表達(dá)這種系統(tǒng)的最佳工具,所以圖論理所當(dāng)然地成為研究Ramsey理論的一個最重要的表達(dá)工具。
　　 自從Ramsey理論誕生以來

3、,經(jīng)歷了70余年的研究歷程,進(jìn)展相當(dāng)緩慢。在Frank Ramsey發(fā)表論文25年之后,人們才得到第一個非平凡的Ramsey結(jié)果[59],在它的研究領(lǐng)域中,懸而未解的問題及猜想相當(dāng)多,因此Ramsey理論成為當(dāng)今圖論工作者的研究熱點(diǎn)之一。人們引入了各種標(biāo)尺來刻劃它,產(chǎn)生了很多研究分支,如一般的Ramsey數(shù),二部Ramsey數(shù),Size Ramsey數(shù)等等；并且它的研究成果已經(jīng)廣泛地應(yīng)用于集合論、幾何、數(shù)論、邏輯學(xué)、計算機(jī)理論研究等多個

4、領(lǐng)域,見文獻(xiàn)[17,77]。
　　 本文第一章和第二章分別介紹了這個領(lǐng)域的相關(guān)定義、研究背景、研究方法、研究進(jìn)展和研究分支。第三章中首先對二部Ramsey數(shù)作進(jìn)一步的研究和推廣,提出了Size Bipartite Ramsey數(shù)的概念,
　　 (br)(B1,B2)=min{e(B):B是二部圖,且B→(B1,B2)},
　　 并將它和Bipartite Ramsey數(shù)進(jìn)行比較,推廣了Erd(o)s和Rousse

5、au[24]關(guān)于對稱二部圖的“計數(shù)引理”,得到結(jié)果如下:
　　 定理0.0.1.設(shè)n≥m≥1是兩個整數(shù),二部圖B有q條邊,q≥m2,則B包含至多個子圖Km,n。
　　 特別地,B包含至多個子圖Kn,n。
　　 針對星圖、對稱二部圖、一般的完全二部圖,本章給出了它們Size BipartiteRamsey數(shù)的上下界。
　　 定理0.0.2.設(shè)m和n是兩個正整數(shù),則
　　 定理0.0.3.對固定的m≥

6、1和充分大的n,有
　　 定理0.0.4.對充分大的n,有
　　 第四章中通過計算邊數(shù)確定的母圖中子圖為完全m-部圖Km(n)的個數(shù),給出了Km(n)的size Ramsey數(shù)[25]的上下界。主要結(jié)論有:
　　 定理0.0.5.設(shè)自然數(shù)n≥2,一個含有q條邊的m-部圖中至多可以誘導(dǎo)出A(m,n,q)個完全m-部圖Km(n)作為子圖,其中
　　 定理0.0.6.設(shè)m、n是兩個整數(shù),m≥2固定,n→∞,那么