關于圖size Ramsey數若干問題的研究.pdf

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

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

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

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

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

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