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

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

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

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

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