不含偶圈C-,2m-的r色Ramsey數(shù)R-,r-(C-,2m-)的下界.pdf

1、Ramsey理論是組合數(shù)學(xué)與圖論的主要研究內(nèi)容之一.Ramsey數(shù)的確定是Ramsey理論中的一個重要研究方向,該問題不僅在數(shù)學(xué)的發(fā)展中有著重要的理論意義,而且在計算機科學(xué)、通信、管理決策等許多領(lǐng)域中也有著實際的應(yīng)用.然而,Ramsey數(shù)的確定是一個NP困難問題,至今人們只計算出了為數(shù)很少的幾個Ramsey數(shù)的精確值.對R個頂點的完全圖K<,R>的每一條邊著由0到r-1中的一種顏色,記其中的著第i種顏色的邊組成的子圖為G<,i>(0≤i

2、≤r-1);如果存在一種著色方法,使得對0≤i≤r-1都有G<,i>不包含圖H,則稱K<,R>對禁止子圖H可r-著色,否則稱K<,R>對禁止子圖H不可r-著色.禁止子圖H的r色Ramsey數(shù)R<,r>(H)是使得K<,R>對H不可r-著色的最小正整數(shù)R.該文討論禁止子圖H為圈的情況.Ronald L. Graham,Burce L. Rothschild與Joel H. Spencer,(Ramsey Theory,Second Edi

3、tion,JOHN WILEY&SONS,1990)證明了:當(dāng)禁止子圖H為奇圈C<,2m+1>時,2<'r>m(C<,2m+1>)<2(r+2)!m;當(dāng)禁止子圖H為偶圈C<,2m>時,R<,r>(C<,2m>)>(r-1)(m-1).該文利用因子分解的理論,給出并證明了Ramsey數(shù)R<,r>(C<,2m>)的一個更優(yōu)的下界:R<,r>(C<,2m>)>Max{(r+1)m-2+(rmod2),2(r-1)(m-1)+1}.