二部圖的幾個Ramsey函數(shù).pdf

1、1930年，英國數(shù)學家Frank Ramsey在其論文《On a problem of formallogic》[90]中得到了后來以他的名字命名的Ramsey定理.特別地，如果一個圖含有足夠多的頂點數(shù)，則該圖含有一個頂點數(shù)為n的團或者頂點數(shù)為n的獨立集.Ramsey定理經(jīng)過許多科學工作者的擴充和推廣，逐步形成了Ramsey理論.作為圖論中一類極值問題，圖的Ramsey理論是當代圖論的一個重要分支.
　　 本文第一章介紹Rams

2、ey理論的起源、研究意義和研究內(nèi)容.
　　 第二章介紹星類圖的Ramsey數(shù).我們得到若G是給定的圖滿足x(G)=k≥2且s(G)=s(這里s(G)是G的色剩余，即G的所有x(G)可著色中最小色部的點數(shù))，并且H是給定的階數(shù)為h的圖，則r(K1+G，K1+nH)≤k(hn+s-1)+1對所有充分大的整數(shù)n成立.特別地，如果s是奇數(shù)或者s是偶數(shù)且hn是奇數(shù)，則r(K1+Kk(s)，K1+nH)=k(hn+s-1)+1.另外，對所有

3、充分大的n，有r(Fs，K1+nH)=2hn+1.
　　 第三章介紹一類含密集圖的Ramsey數(shù)及其二部形式.第一部分我們分別給出了一個二部Ramsey數(shù)的階以及一個二部Ramsey數(shù)的界.我們得到若t≥1是給定的整數(shù)，則br(Kt，n，Kn，n)的階是nt+1/(logn)t.另外，若H是給定的具有色部為(A，B)階數(shù)為h的二部圖，且滿足△(B)≤t，則對所有充分大的n，有br(H，Kn，n)≤(hn/logn)t(logn)

4、a(t)，其中a(1)=a(2)=1，a(t)=0若t≥3.第二部分我們獲得了brk(C4；Kn，n)的階是n2/log2n對k≥3都成立，且br2(C4；Kn，n)≥c(nloglogn/log2 n)2對充分大的n成立.第三部分我們給出了一個Ramsey數(shù)的下界，這個界漸近可達.設v(F)和e(F)分別表示圖F的階數(shù)和邊數(shù)，p(F)=e(F)-1/V(F)-2.我們得到若F是給定的連通圖，Gn是一列階數(shù)為n平均度是dn≥2的圖，則存