關(guān)于路和圈的3-色Ramsey數(shù)

陳 明， 李雨生

(1. 同濟(jì)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 上海 200092; 2. 嘉興學(xué)院 數(shù)理與信息工程學(xué)院， 浙江 嘉興 314000)

1 研究背景

本文研究的圖均為簡單無向圖.設(shè)G是一個圖,其點(diǎn)集和邊集分別為V(G)和E(G)，并分別用n(G)、Δ(G)和δ(G)表示圖G的階數(shù)、最大度以及最小度.Pn和Cn分別表示由n個點(diǎn)構(gòu)成的路和圈.圖G中最大的圈長稱為該圖的周長，用c(G)來表示.其他有關(guān)圖的定義，可參考文獻(xiàn)[1].

對于給定的圖G1，G2，…，Gk，k≥2，k-色Ramsey數(shù)R(G1，G2，…，Gk)是指最小的正整數(shù)n，使得對n個點(diǎn)的完全圖進(jìn)行任意的k-邊染色，總是存在某個染i色的單色圖Gi，1≤i≤k.若G1=G2=…=Gk=G，k-色Ramsey數(shù)R(G1，G2，…，Gk)簡記為Rk(G)，又稱之為G的對角k-色Ramsey數(shù).當(dāng)k=2時，2-色Ramsey數(shù)通常簡稱為Ramsey數(shù).

關(guān)于Ramsey數(shù)的研究成果非常豐富，詳細(xì)可見動態(tài)綜述文獻(xiàn)[2].但對于k-色Ramsey數(shù)(k≥3)的研究結(jié)果相對較少，并且主要集中在對路和圈等結(jié)構(gòu)比較明確的圖的研究上.對于充分大的路和圈，其對角3-色Ramsey數(shù)已經(jīng)明確：

定理1[3]設(shè)n充分大，則R3(Pn)= 2n-2+(nmod 2);

定理2[4]設(shè)n是一個充分大的偶數(shù)，則有R3(Cn)= 2n;

定理3[5]設(shè)n是一個充分大的奇數(shù)，則有R3(Cn)= 4n-3.

對于任意的n，很多學(xué)者猜測定理1～3也是成立的，但目前僅有少數(shù)情況得到驗(yàn)證.

對于路和圈的混合3-色Ramsey數(shù)，已有學(xué)者給出了一些準(zhǔn)確值：

定理4[6]設(shè)n≥6，則R(P3,P3,Cn)=n;

定理5[7]設(shè)n≥6，則R(P4,P4,Cn)=n+2;

定理6[8]設(shè)n≥23，則R(P4,P5,Cn)=n+2，R(P4,P6,Cn)=n+3;

R(Pm,Pn,Ck)=2n+2m2-3

在此基礎(chǔ)上，本文證明了：

定理9設(shè)m為奇數(shù)，n>2m2-7m+8, 則R(Pm,Pm,Cn)=m+n-3.

2 主要結(jié)果的證明

為了證明定理8和定理9，將用到以下術(shù)語符號和定理.

r(a,b)=a-bab=a mod b.

定理11[11]設(shè)G是一個有n個點(diǎn)和m條邊的圖，m≥n，且周長c(G)=k.則m≤w(n,k).

2.1 定理8的證明

當(dāng)m≤4時，由定理5可知結(jié)論成立.以下設(shè)m≥6 .

再證R(Pm,Pm,Cn)≤m+n-2，令N=m+n-2，只需證明任意3-邊染色(三種顏色設(shè)為紅、藍(lán)和綠)的KN，至少含有紅色的Pm、藍(lán)色的Pm和綠色的Cn中之一.方便起見，分別稱紅(藍(lán)、綠)邊導(dǎo)出的子圖為紅(藍(lán)、綠)子圖.下面假設(shè)某3-邊染色的KN，不含有紅色的Pm，不含藍(lán)色的Pm，也不含綠色的Cn，從而導(dǎo)出矛盾.

因?yàn)榫G子圖中不含有Cn，由定理10可知，綠子圖的周長最大為n-1.再根據(jù)定理11，可知KN中綠邊的條數(shù)至多為

2.2 定理9的證明

當(dāng)m=3時，由定理4可知結(jié)論成立.以下設(shè)m≥5 .

再證R(Pm,Pm,Cn)≤m+n-3，令N=m+n-3，只需證明任意3-邊染色(三種顏色設(shè)為紅、藍(lán)和綠)的KN，至少含有紅色的Pm、藍(lán)色的Pm和綠色的Cn中之一.方便起見，分別稱紅(藍(lán)、綠)邊導(dǎo)出的子圖為紅(藍(lán)、綠)子圖.下面假設(shè)某3-邊染色的KN，不含有紅色的Pm，不含藍(lán)色的Pm，也不含綠色的Cn，從而導(dǎo)出矛盾.

因?yàn)榫G子圖中不含有Cn，由定理10可知，綠子圖的周長最大為n-1.再根據(jù)定理11，可知KN中綠邊的條數(shù)至多為

這和題設(shè)中的n>2m2-7m+8矛盾，定理9證畢.

鑒于目前所有的研究，給出一個大膽的猜測：

猜想對任意正整數(shù)n和m,且n≥m, 有R(Pm,Pm,Cn)=m+n-2-(mmod 2).