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

陳 明， 李雨生

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

1 研究背景

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

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

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

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

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

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

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

對(duì)于路和圈的混合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ù)語(yǔ)符號(hào)和定理.

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

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

2.1 定理8的證明

當(dāng)m≤4時(shí)，由定理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中之一.方便起見(jiàn)，分別稱紅(藍(lán)、綠)邊導(dǎo)出的子圖為紅(藍(lán)、綠)子圖.下面假設(shè)某3-邊染色的KN，不含有紅色的Pm，不含藍(lán)色的Pm，也不含綠色的Cn，從而導(dǎo)出矛盾.

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

2.2 定理9的證明

當(dāng)m=3時(shí)，由定理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中之一.方便起見(jiàn)，分別稱紅(藍(lán)、綠)邊導(dǎo)出的子圖為紅(藍(lán)、綠)子圖.下面假設(shè)某3-邊染色的KN，不含有紅色的Pm，不含藍(lán)色的Pm，也不含綠色的Cn，從而導(dǎo)出矛盾.

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

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

鑒于目前所有的研究，給出一個(gè)大膽的猜測(cè)：

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