2. 嘉兴学院 数理与信息工程学院,浙江 嘉兴 314000
2. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing Zhejiang 314000, China
本文研究的图均为简单无向图.设G是一个图, 其点集和边集分别为V(G)和E(G),并分别用n(G)、Δ(G)和δ(G)表示图G的阶数、最大度以及最小度.Pn和Cn分别表示由n个点构成的路和圈.图G中最大的圈长称为该图的周长,用c(G)来表示.其他有关图的定义,可参考文献[1].
对于给定的图G1,G2,…,Gk,k≥2,k-色Ramsey数R(G1,G2,…,Gk)是指最小的正整数n,使得对n个点的完全图进行任意的k-边染色,总是存在某个染i色的单色图Gi,1≤i≤k.若G1=G2=…=Gk=G,k-色Ramsey数R(G1,G2,…,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] 设m,n,k是正整数.若满足k≥3是一个奇数,n≥k,且m为奇数时
$ R({P_m}, {P_n}, {C_k}) = 2n + 2\left\lfloor {\frac{m}{2}} \right\rfloor-3 $ |
在此基础上,本文证明了:
定理8 设m为偶数,
定理9 设m为奇数,n>2m2-7m+8, 则R(Pm, Pm, Cn)=m+n-3.
2 主要结果的证明为了证明定理8和定理9,将用到以下术语符号和定理.
设a和b是正整数,定义
定理10[10] 设G是一个有n个点的非二部图,若它的边数超过
定理11[11] 设G是一个有n个点和m条边的图,m≥n,且周长c(G)=k.则m≤w(n, k).
2.1 定理8的证明当m≤4时,由定理5可知结论成立.以下设m≥6.
先证R(Pm, Pm, Cn)≥m+n-2.设Km+n-3是m+n-3个点构成的完全图,把其点集分成三部分X、Y和Z,其中|X|=n-1,
再证R(Pm, Pm, Cn)≤m+n-2,令N= m+n-2,只需证明任意3-边染色(三种颜色设为红、蓝和绿)的KN,至少含有红色的Pm、蓝色的Pm和绿色的Cn中之一.方便起见,分别称红(蓝、绿)边导出的子图为红(蓝、绿)子图.下面假设某3-边染色的KN,不含有红色的Pm,不含蓝色的Pm,也不含绿色的Cn,从而导出矛盾.
假设绿子图是一个二部图.因为m≥6,故
绿色子图不是一个二部图.由于3-边染色的KN中不含有红色的Pm,由路的Turán数可知,红边至多有
$ \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的总边数
$ \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} $ |
这和题设中的
当m=3时,由定理4可知结论成立.以下设m≥5.
先证R(Pm, Pm, Cn)≥m+n-3.设Km+n-4是m+n-4个点构成的完全图,将其点集分成三部分X、Y和Z,其中|X|=n-1, |Y|=|Z|=
再证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.因此,在该二部图中至少有一个部集的点数至少为
绿色子图不是一个二部图.由于3-边染色的KN中不含有红色的Pm,由路的Turán数可知,红边至多有
$ \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的总边数
$ \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证毕.
鉴于目前所有的研究,给出一个大胆的猜测:
猜想 对任意正整数n和m, 且n≥m, 有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 |