论文部分内容阅读
1930年,英国数学家Frank Ramsey在其论文《On a problem of formallogic》[90]中得到了后来以他的名字命名的Ramsey定理.特别地,如果一个图含有足够多的顶点数,则该图含有一个顶点数为n的团或者顶点数为n的独立集.Ramsey定理经过许多科学工作者的扩充和推广,逐步形成了Ramsey理论.作为图论中一类极值问题,图的Ramsey理论是当代图论的一个重要分支.
本文第一章介绍Ramsey理论的起源、研究意义和研究内容.
第二章介绍星类图的Ramsey数.我们得到若G是给定的图满足x(G)=k≥2且s(G)=s(这里s(G)是G的色剩余,即G的所有x(G)可着色中最小色部的点数),并且H是给定的阶数为h的图,则r(K1+G,K1+nH)≤k(hn+s-1)+1对所有充分大的整数n成立.特别地,如果s是奇数或者s是偶数且hn是奇数,则r(K1+Kk(s),K1+nH)=k(hn+s-1)+1.另外,对所有充分大的n,有r(Fs,K1+nH)=2hn+1.
第三章介绍一类含密集图的Ramsey数及其二部形式.第一部分我们分别给出了一个二部Ramsey数的阶以及一个二部Ramsey数的界.我们得到若t≥1是给定的整数,则br(Kt,n,Kn,n)的阶是nt+1/(logn)t.另外,若H是给定的具有色部为(A,B)阶数为h的二部图,且满足△(B)≤t,则对所有充分大的n,有br(H,Kn,n)≤(hn/logn)t(logn)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数的下界,这个界渐近可达.设v(F)和e(F)分别表示图F的阶数和边数,p(F)=e(F)-1/V(F)-2.我们得到若F是给定的连通图,Gn是一列阶数为n平均度是dn≥2的图,则存在常数c=c(F)>0,对所有充分大的n,有r(F,Gn)≥c(dn/logdn)p(F).
第四章介绍轮对圈的Ramsey数.我们得到当m是奇数且n≥m≥1002时,有r(Wm,Cn)=3n-1.另外,当m≥4是偶数时,则对所有的整数n≥3m/2+5,有r(Wm,Cn)=2n-1;特别地,r(Wm,Cn)=2n-1若m,n都是偶数且n≥m+500.