关于路和圈的3-色Ramsey数
文章快速检索    
  同济大学学报(自然科学版)  2018, Vol. 46 Issue (7): 988-990.  DOI: 10.11908/j.issn.0253-374x.2018.07.018
0

引用本文  

陈明, 李雨生. 关于路和圈的3-色Ramsey数[J]. 同济大学学报(自然科学版), 2018, 46(7): 988-990. DOI: 10.11908/j.issn.0253-374x.2017.05.002.
CHEN Ming, LI Yusheng. On Some Three-color Ramsey Numbers of Paths and Cycles[J]. Journal of Tongji University (Natural Science), 2018, 46(7): 988-990. DOI: 10.11908/j.issn.0253-374x.2018.07.018.

基金项目

国家自然科学基金(11331003),浙江省自然科学基金(LY17F030020),浙江省嘉兴市科技局项目(2016AY13011)

第一作者

陈明(1981—),男,博士生,讲师,主要研究方向为组合数学与图论.E-mail: chen2001ming@163.com

通讯作者

李雨生(1954—),男,理学博士,教授,博士生导师,主要研究方向为组合数学与图论.E-mail:li_yusheng@tongji.edu.cn

文章历史

收稿日期:2017-11-14
关于路和圈的3-色Ramsey数
陈明1,2, 李雨生1    
1. 同济大学 数学科学学院,上海 200092;
2. 嘉兴学院 数理与信息工程学院,浙江 嘉兴 314000
摘要:对于给定的图G1G2,…,Gk, k≥2,k-色Ramsey数R(G1G2,…,Gk)是指最小的正整数n,使得对n个点的完全图进行任意的k-边染色,总是存在某个染i色的单色图Gi,1≤ik.对G1=G2= PmG3= Cn的情况进行了研究,得到了n较大时的3-色Ramsey数R(Pm, Pm, Cn)的准确值.
关键词        3-色Ramsey数    
On Some Three-color Ramsey Numbers of Paths and Cycles
CHEN Ming1,2, LI Yusheng1     
1. School of Mathematical Sciences, Tongji University, Shanghai 200092, China;
2. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing Zhejiang 314000, China
Abstract: For given graphs G1, G2, …, Gk, where k≥2, the k-color Ramsey number R(G1, G2, …, Gk)is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, there is always a monochromatic copy of Gi colored with color i, for some 1≤ik. In this note, we provide the exact value for 3-color Ramsey R(Pm, Pm, Cn), where n is larger than m.
Key words: path    cycle    3-color Ramsey number    
1 研究背景

本文研究的图均为简单无向图.设G是一个图, 其点集和边集分别为V(G)和E(G),并分别用n(G)、Δ(G)和δ(G)表示图G的阶数、最大度以及最小度.PnCn分别表示由n个点构成的路和圈.图G中最大的圈长称为该图的周长,用c(G)来表示.其他有关图的定义,可参考文献[1].

对于给定的图G1G2,…,Gkk≥2,k-色Ramsey数R(G1G2,…,Gk)是指最小的正整数n,使得对n个点的完全图进行任意的k-边染色,总是存在某个染i色的单色图Gi,1≤ik.若G1=G2=…=Gk=Gk-色Ramsey数R(G1G2,…,Gk)简记为Rk(G),又称之为G的对角k-色Ramsey数.当k=2时,2-色Ramsey数通常简称为Ramsey数.

关于Ramsey数的研究成果非常丰富,详细可见动态综述文献[2].但对于k-色Ramsey数(k≥3)的研究结果相对较少,并且主要集中在对路和圈等结构比较明确的图的研究上.对于充分大的路和圈,其对角3-色Ramsey数已经明确:

定理1[3]  设n充分大,则R3(Pn)= 2n-2+(n mod 2);

定理2[4]  设n是一个充分大的偶数,则有R3(Cn)= 2n;

定理3[5]  设n是一个充分大的奇数,则有R3(Cn)= 4n-3.

对于任意的n,很多学者猜测定理1~3也是成立的,但目前仅有少数情况得到验证.

对于路和圈的混合3-色Ramsey数,已有学者给出了一些准确值:

定理4[6]  设n≥6,则R(P3, P3, Cn)=n;

定理5[7]  设n≥6,则R(P4, P4, Cn)=n+2;

定理6[8]  设n≥23,则R(P4, P5, Cn)=n+2,R(P4, P6, Cn)=n+3;

定理7[9]  设mnk是正整数.若满足k≥3是一个奇数,nk,且m为奇数时$n > \frac{{3{m^2} - 14m + 25}}{4}$m为偶数时,$n > \frac{{3{m^2} - 10m + 20}}{8}$,则:

$ R({P_m}, {P_n}, {C_k}) = 2n + 2\left\lfloor {\frac{m}{2}} \right\rfloor-3 $

在此基础上,本文证明了:

定理8  设m为偶数,$n > \frac{{2{m^2}-5m + 7}}{3}$, 则R(Pm, Pm, Cn)=m+n-2;

定理9  设m为奇数,n>2m2-7m+8, 则R(Pm, Pm, Cn)=m+n-3.

2 主要结果的证明

为了证明定理8和定理9,将用到以下术语符号和定理.

ab是正整数,定义$r(a, b) = a-b\left\lfloor {\frac{a}{b}} \right\rfloor = a\; \bmod \; b$.对于整数nk≥3,定义:$w(n, k) = \frac{1}{2}(n-1)k-\frac{1}{2}r(k-r - 1)$, 其中r=r(n-1, k-1).

定理10[10]  设G是一个有n个点的非二部图,若它的边数超过$\frac{{{{(n-1)}^2}}}{4} + 1$,则图G含有从3到最大长的所有长度的圈.

定理11[11]  设G是一个有n个点和m条边的图,mn,且周长c(G)=k.则mw(n, k).

2.1 定理8的证明

m≤4时,由定理5可知结论成立.以下设m≥6.

先证R(Pm, Pm, Cn)≥m+n-2.设Km+n-3m+n-3个点构成的完全图,把其点集分成三部分XYZ,其中|X|=n-1, $\left| Y \right| = \left| Z \right| = \frac{{m-2}}{2}$.现对Km+n-3进行如下的3-边染色(三种颜色设为红、蓝和绿):XYZ内部的边,以及YZ之间的边都染绿色,XY之间的边都染蓝色,XZ之间的边都染红色.很明显在这个3-边染色的Km+n-3中,不含有红色的Pm,也不含有蓝色的Pm,还不含有绿色的Cn.因此,由3-色Ramsey数的定义可知R(Pm, Pm, Cn)≥m+n-2.

再证R(Pm, Pm, Cn)≤m+n-2,令N= m+n-2,只需证明任意3-边染色(三种颜色设为红、蓝和绿)的KN,至少含有红色的Pm、蓝色的Pm和绿色的Cn中之一.方便起见,分别称红(蓝、绿)边导出的子图为红(蓝、绿)子图.下面假设某3-边染色的KN,不含有红色的Pm,不含蓝色的Pm,也不含绿色的Cn,从而导出矛盾.

假设绿子图是一个二部图.因为m≥6,故$n > \frac{{2{m^2}-5m + 7}}{3} > 2m$.因此,在该二部图中至少有一个部集的点数至少为$\frac{{3m-2}}{2}$.因为m为偶数时,$R({P_m}, {P_m}) = \frac{{3m-2}}{2}$,所以该部集的导出子图要么含有一个红色Pm,要么含有一个蓝色Pm,矛盾.

绿色子图不是一个二部图.由于3-边染色的KN中不含有红色的Pm,由路的Turán数可知,红边至多有$\frac{{m-2}}{2}N$条.类似地,蓝边也至多有$\frac{{m-2}}{2}N$条.因此,绿子图的边数至少为$\frac{{N(N-1)}}{2}-2\frac{{m-2}}{2} \cdot N$.易验证,当$n > \frac{{2{m^2}-5m + 7}}{3}(m \ge 6)$时,有:

$ \frac{{N(N-1)}}{2}-2 \cdot \frac{{m-2}}{2}N > \frac{{{{(N - 1)}^2}}}{4} + 1 $

因为绿子图中不含有Cn,由定理10可知,绿子图的周长最大为n-1.再根据定理11,可知KN中绿边的条数至多为

$ \begin{array}{l} w(N, n-1) = \frac{1}{2}(N-1)(n-2) - \frac{1}{2}(m - 1)(n - \\ 1(m - 1) - 1) \end{array} $

因此,该3-边染色的KN的总边数$\frac{{N(N-1)}}{2}$满足:

$ \begin{array}{l} \frac{{N(N-1)}}{2} \le 2 \cdot \frac{{m-2}}{2}N + w(N, n-1) = \\ (m - 2)N - \frac{1}{2}(N - 1)(n - 2) - \frac{1}{2}(m\\ - 1)(n - m - 1) \end{array} $

这和题设中的$n > \frac{{2{m^2}-5m + 7}}{3}$矛盾,定理8证毕.

2.2 定理9的证明

m=3时,由定理4可知结论成立.以下设m≥5.

先证R(Pm, Pm, Cn)≥m+n-3.设Km+n-4m+n-4个点构成的完全图,将其点集分成三部分XYZ,其中|X|=n-1, |Y|=|Z|=$\frac{{m-3}}{2}$.现对Km+n-4进行如下的3-边染色(三种颜色设为红、蓝和绿):XYZ内部的边,以及YZ之间的边都染绿色,XY之间的边都染蓝色,XZ之间的边都染红色.很明显在这个3-边染色的Km+n-4中,不含有红色的Pm,也不含有蓝色的Pm,还不含有绿色的Cn.因此,由3-色Ramsey数的定义可知R(Pm, Pm, Cn)≥m+n-3.

再证R(Pm, Pm, Cn)≤m+n-3,令N= m+n-3,只需证明任意3-边染色(三种颜色设为红、蓝和绿)的KN,至少含有红色的Pm、蓝色的Pm和绿色的Cn中之一.方便起见,分别称红(蓝、绿)边导出的子图为红(蓝、绿)子图.下面假设某3-边染色的KN,不含有红色的Pm,不含蓝色的Pm,也不含绿色的Cn,从而导出矛盾.

假设绿子图是一个二部图.因为m≥5,故n>2m2-7m+8>2m.因此,在该二部图中至少有一个部集的点数至少为$\frac{{3m-3}}{2}$.因为m为奇数时,R(Pm, Pm)=$\frac{{3m-3}}{2}$,所以该部集的导出子图要么含有一个红色Pm,要么含有一个蓝色Pm,矛盾.

绿色子图不是一个二部图.由于3-边染色的KN中不含有红色的Pm,由路的Turán数可知,红边至多有$\frac{{m-2}}{2}N$条.类似地,蓝边也至多有$\frac{{m-2}}{2}N$条.因此,绿子图的边数至少为:$\frac{{N(N-1)}}{2}-2 \cdot \frac{{m-2}}{2}N$.易验证,当n>2m2-7m+8(m≥5)时,有:

$ \frac{{N(N-1)}}{2}-2 \cdot \frac{{m-2}}{2}N > \frac{{{{(n - 1)}^2}}}{4} + 1 $

因为绿子图中不含有Cn,由定理10可知,绿子图的周长最大为n-1.再根据定理11,可知KN中绿边的条数至多为

$ w\left( {N, n-1} \right) = \frac{1}{2}\left( {N-1} \right)\left( {n-2} \right) - \frac{1}{2}\left( {m - 2} \right)\left( {n - 1 - \left( {m - 2} \right) - 1} \right) $

因此,该3-边染色的KN的总边数$\frac{{N(N-1)}}{2}$满足:

$ \begin{array}{l} \frac{{N\left( {N-1} \right)}}{2} \le 2\cdot\frac{{m-2}}{2}N + w\left( {N, n-1} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {m - 2} \right)N + \frac{1}{2}\left( {N - 1} \right)\left( {n - 2} \right) - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{2}\left( {m - 2} \right)\left( {n - m} \right) \end{array} $

这和题设中的n>2m2-7m+8矛盾,定理9证毕.

鉴于目前所有的研究,给出一个大胆的猜测:

猜想  对任意正整数nm, 且nm, 有R(Pm, Pm, Cn)=m+n-2-(m mod 2).

参考文献
[1]
BOLLOBÁS B. Modern graph theory [M]. New York: Spring-Verlag, 1998.
[2]
RADZISZOWSKI S P. Small ramsey numbers[J]. Electronic Journal of Combinatorics, 2011, 1(4): 28
[3]
GYÁRFS A, RUSZINKÓ M, SÁKÖZY G N, et al. Three color ramsey numbers for paths[J]. Combinatorica, 2007, 27(1): 35 DOI:10.1007/s00493-007-0043-4
[4]
BENEVIDES F S, SKOKAN J. The 3-colored ramsey number of even cycles[J]. Journal of Combinatorial Theory, Series B, 2009, 99(4): 690 DOI:10.1016/j.jctb.2008.12.002
[5]
KOHAYAKAWA Y, SIMONOVITS M, SKOKAN J. The 3-colored Ramsey number of odd cycles[J]. Electronic Notes in Discrete Mathematics, 2005, 19: 397 DOI:10.1016/j.endm.2005.05.053
[6]
DZIDO T. Multicolor ramsey numbers for paths and cycles[J]. Discussiones Mathematicae Graph Theory, 2005, 25(1-2): 57 DOI:10.7151/dmgt
[7]
DZIDO T, KUBALE M, PIWAKOWSKI K. On some ramsey and turán-type numbers for paths and cycles[J]. The Electronic Journal of Combinatorics, 2006, 13: R55
[8]
SHAO Zehui, XU Xiaodong, SHI Xiaolong, et al. Some three-color Ramsey numbers, R (P4, P5, Ck) and R (P4, P6, Ck)[J]. European Journal of Combinatorics, 2009, 30(2): 396 DOI:10.1016/j.ejc.2008.05.008
[9]
DZIDO T, FIDYTEK R. On some three color ramsey numbers for paths and cycles[J]. Discrete Mathematics, 2009, 309(15): 4955 DOI:10.1016/j.disc.2008.04.053
[10]
BRANDT S. A sufficient condition for all short cycles[J]. Discrete Applied Mathematics, 1997, 79(1-3): 63 DOI:10.1016/S0166-218X(97)00032-2
[11]
CACCETTA L, VIJAYAN K. Maximal cycles in graphs[J]. Discrete Mathematics, 1991, 98(1): 1 DOI:10.1016/0012-365X(91)90407-S