论文部分内容阅读
1928年,英国数学家Frank Ramsey提出了Ramsey定理的概念,表明若将一个充分大的结构分割成若干个有限的子结构,其某个子结构必然具有某种特殊性质.随后,Ramsey定理从几个看似孤立的定理不断发展形成了Ramsey理论,图的Ramsey数是Ramsey理论的推广,它作为图论的一个著名难题一直备受瞩目.本文主要讨论图的二部Ramsey数,多色Ramsey数和Ramsey数.若G1,…,Gk为一组二部图,图的二部Ramsey数br(G1,…,Gk)为最小的正整数N使得对完全二部图KN,N的边任意k着色,一定会存在某个单色Gi(i=1,…k).此外,对于给定的图G1,…,Gk,图的多色Ramsey数R(G1,…,Gk)为最小的正整数N使得对N阶完全图KN的边任意n着色,都会存在某个单色子图Gi(i=1,…,k).一般情况下,图的Ramsey数特指k=2.本文分为五章,第一章主要介绍Ramsey数的发展历程及本文的主要结果.第二章是本文的重点,给出了平衡(β,△)-图H的二部Ramsey数.即令0<γ<1,▲≥>1为任意选定的自然数,则一定存在β=β(γ,△)>0和正整数n0使得对任意给定的平衡(β,△)-图H,若|H|=n≥n0,有br(H,H)≤(1+γ/3)n.特别地,当n充分大时,有br(C2n,C2n)=(2+o(1))n.此外,对于br(H,…,H)也有类似的结果成立.第三章给出了固定图对多条路的多色Ramsey数.选定H,Pni表示阶数为ni的路(1≤i≤t).当t=1时,令n1≥4丨H丨,当t≥2时,令nt≥4R(Pnl,…,Pnt-l,H).则R(Pn1,…,Pnt,H)=(χ(H)-1(nt-t+∑「ni/2」)+σ(H).对连通图G1,…,Gn和一组阶为pt的连通图Hpi,令r=R(G1,…,Gn)且r1=R(Hp1,…Hpm),若l≥2,R(G1,…,Gn,K1)=(r-1)(l-1)+1,则R(G1,…,Gn,Hp1,…Hpm)≤(r-1)(r’-1)+1.当Hp1=Kp1,…,Hpm=Kpm时,等号成立.第四章给出了轮图对轮图的Ramsey数取值范围.可知若n为奇数,m≥n≥3且m≥5,则3m+1≤R(Wm,Wn)≤8m-3.右n为偶数且m≥n+502,则2m+1≤R(Wm,Wn)≤7-2.五章对本文进行了总结并提出了未来可研究的方向.