涉及密集圖的幾個Ramsey數(shù).pdf

1、圖論是研究由若干點及連接點的邊所組成的圖的科學(xué),是數(shù)學(xué)的一個分支,屬于應(yīng)用數(shù)學(xué)的一部分。圖論是一門古老而又新興的科學(xué),他的起源很早,早在1736年,著名的數(shù)學(xué)家L.Euler就在K(o)nigsberg七橋問題上用圖的方法解決了這個問題,并開創(chuàng)了一門學(xué)科--圖論。而Ramsey理論作為圖論中一個極值問題,是比較難的分支。1930年英國數(shù)學(xué)家Frank Ramsey在論文《On a problem of formal logic》[81]

2、中得到了后來以他的名字命名的Ramsey定理。這個定理經(jīng)過后來科學(xué)工作者的擴(kuò)充和推廣,逐步形成了一個理論,那就是Ramsey理論,它的研究內(nèi)容就是:在某種條件下,無論對一個大系統(tǒng)(結(jié)構(gòu))如何進(jìn)行分割,總是存在人們預(yù)期想要得到的子系統(tǒng)(結(jié)構(gòu)),這種大系統(tǒng)的最小階便稱之為Ramsey數(shù)。由于Ramsey理論中存在許多問題,使之成為當(dāng)代圖論的一個重要分支。
　　 然而,Ramsey理論中研究的問題的都具有很大的難度。自Ramsey的第

3、一篇相關(guān)文章發(fā)表以來,進(jìn)展十分緩慢。因此,科學(xué)工作者就另辟蹊徑,產(chǎn)生出了很多分支,如邊Ramsey數(shù)、二部Ramsey數(shù)、混合Ramsey數(shù)、推廣Ramsey數(shù)等等。直到近一二十年,隨著分析、概率、代數(shù)等高等方法的運(yùn)用,出現(xiàn)了很多新的結(jié)果,同時,Ramsey理論也開始應(yīng)用到集合論、幾何、數(shù)論、邏輯學(xué)、計算機(jī)理論研究等其他領(lǐng)域,成為當(dāng)今數(shù)學(xué)界研究的一個熱點。
　　 本文第一章介紹了這個領(lǐng)域的相關(guān)定義、研究背景、研究方法、研究進(jìn)展和

4、研究分支。第二章運(yùn)用代數(shù)學(xué)中有限域的構(gòu)造,給出了完全圖去掉一條邊這類圖Ramsey數(shù)的下界,并得到了在特殊情況下r(K2,n)的表達(dá)式。第三章給出了推廣Ramsey數(shù)的存在條件和一個一般的上界。第四章用概率的方法給出了二部Ramsey數(shù)的最小值和圖的邊數(shù)之間的關(guān)系。記Gn為階為p的Paley圖,第二章中我們構(gòu)造了圖Hp,給出了下述結(jié)論。
　　 定理0.0.1.如果Hp包含Ks-e做為子圖,則Gp肯定包含Ks-1-e做為子圖。