New lower bounds of fifteen classical Ramsey numbers
New lower bounds of fifteen classical Ramsey numbers
复制标题
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
W. Su;Haipeng Luo;Zhengyou Zhang;Guiqing Li
中科院分区：
文献类型：
--
作者：
W. Su;Haipeng Luo;Zhengyou Zhang;Guiqing Li
开发了一种计算经典拉姆齐数 R(Ql' Q2," " Qn) 下界的算法。将十五个素数阶完全图分别构造成n个循环图，并通过计算机搜索研究它们的性质。这导致八个多色和七个二色拉姆齐数的新下界，即 R(3, 3, 6) 2: 54、R(3, 3, 7) 2: 72、R(3, 3, 9) 2: 1l0、R(3, 3, ll) 2: 138、R(3, 3, 3, 5) 2: 1l0， R(3,3,3,6)2:138,R(3,3,3,7)2:194,R(3,3,4,4)~114和R(4,19)2:194,R(4,20)2:230,R(4,21)2:242,R(5,17) 2: 282, R(5, 19) 2: 338, R(6, 17) 2: 500, R(7, 17) 2: 548. *广西自然科学基金委资助 广西计算中心客座教授 Australasian Journal of Combinatorics 19(1999), pp.91-99 经典拉姆齐数 R(ql, q2,' ", qn) (对于 n 2: 2) 是最小的整数 r，使得如果 r 阶完全图 Kr 的边用 n 种颜色着色，那么对于某些 i E {I, 2, ... ,n} 存在单色 K q;。到目前为止，只找到了 9 个 2 色 Ramsey 数的精确值。最佳下界的数量不超过 40 个（参见[11））。在我们的结果之前，没有当 ql 2: 4 和 q2 ~ 16 已知时，R(ql, q2) 的非平凡下界如下是我们之前获得的两个结果： R(4,12) 2: 128 [13] R(6, 12) ~ 224 [7]。已找到多色拉姆齐数：R(3,3,3) = 17 [4]。已找到一些非平凡的下限和上限，主要是通过计算机找到的，例如： 30 ~ R(3, 3, 4) :::; 31 45 ~ R(3,3,5):::; 57 55 ~ R(3, 4, 4) :::; 79 87 ~ R(3, 3, 3, 4) :::; 155 80 ~ R(3, 4, 5) :::; 161 我们自己得到：[5,10] [1,6,2] [6,2] [2,3] [2,3]. 458 :::; R( 4,4,4,4) [12] 90 :::; R(3, 3, 9) [8] 108 :::; R(3, 3,11) [9] ，请参阅权威的动态调查[11]，该论文也提供了许多参考文献，该算法基于素数阶循环图，非常有效，得到了以下 15 个新的下界，其中 8 个是多色 Ramsey 数的下界，另外 7 个是 Radziszowski [11] 引用的。对于2色定理1 R(3, 3, 6) ~ 54, R(3, 3, 7) ~ 72, R(3, 3, 9) 2: 110, R(3, 3, 11) ~ 138, R(3, 3, 3, 5) 2: 110, R(3, 3, 3, 6) ~ 138, R(3,3,3,7)2:194,R(3,3,4,4)~114;R(4,19)~194,R(4,20)2:230,R(4,21)~242,R(5,17)~282,R(5,19)2:338,R(6,17)~ 500, R(7, 17) 2: 548. 1 素数阶循环图 对于给定的素数整数 p = 2m+l，令 Zp {-m,···, -1,0,1, ... , m} = [-m, m]。（对于 s ~ t，我们用 [8, t] 表示集合 {8, 8 + 1"", t}。）在本文的其余部分，除非相反，暗示所有整数都将被视为 Zp 的成员，
An algorithm to compute lower bounds for the classical Ramsey numbers R(Ql' Q2," " Qn) is developed. The decompositions of each of fifteen complete graphs of prime order into n circulant graphs are constructed and their properties are studied by computer search. This leads to new lower bounds of eight multicolor and seven 2-color Ramsey numbers, namely, R(3, 3, 6) 2: 54, R(3, 3, 7) 2: 72, R(3, 3, 9) 2: 1l0, R(3, 3, ll) 2: 138, R(3, 3, 3, 5) 2: 1l0, R(3, 3, 3, 6) 2: 138, R(3, 3, 3, 7) 2: 194, R(3, 3, 4, 4) ~ 114 and R( 4,19) 2: 194, R( 4,20) 2: 230, R( 4,21) 2: 242, R(5, 17) 2: 282, R(5, 19) 2: 338, R(6, 17) 2: 500, and R(7, 17) 2: 548. *Research supported by Guangxi Natural Science Foundation tVisiting professor in Guangxi Computing Center Australasian Journal of Combinatorics 19(1999), pp.91-99 The classical Ramsey number R(ql, q2,' ", qn) (for n 2: 2) is the smallest integer r such that if the edges of Kr, the complete graph of order r, are colored with n colors, then for some i E {I, 2, ... ,n} there is a monochromatic K q;. Only nine exact values of 2-color Ramsey numbers have been found up to now. The number of best lower bounds is no more than 40 (see [11)). Prior to our results, no non-trivial lower bounds for R(ql, q2) when ql 2: 4 and q2 ~ 16 were known. The following are two of the results we obtained previously: R( 4,12) 2: 128 [13] R(6, 12) ~ 224 [7]. When n 2: 3, less is known about R(ql, q2," " qn). So far, only one exact value of a multicolor Ramsey number has been found: R(3,3,3) = 17 [4]. Some non-trivial lower and upper bounds have been found, mostly by computer, for example: 30 ~ R(3, 3, 4) :::; 31 45 ~ R(3,3,5):::; 57 55 ~ R(3, 4, 4) :::; 79 87 ~ R(3, 3, 3, 4) :::; 155 80 ~ R(3, 4, 5) :::; 161 We ourselves obtained the following: [5,10] [1,6,2] [6,2] [2,3] [2,3]. 458 :::; R( 4,4,4,4) [12] 90 :::; R(3, 3, 9) [8] 108 :::; R(3, 3,11) [9]. For details, please refer to the authoritative dynamic survey [11], which also provides many references. In this paper, we present a new algorithm to compute bounds on classical Ramsey numbers. The algorithm is based on circulant graphs of prime order. It is so efficient that the following fifteen new lower bounds are obtained, of which eight are for multicolor Ramsey numbers and the other seven (which have been quoted by Radziszowski [11]) are for 2-color ones. Theorem 1 R(3, 3, 6) ~ 54, R(3, 3, 7) ~ 72, R(3, 3, 9) 2: 110, R(3, 3, 11) ~ 138, R(3, 3, 3, 5) 2: 110, R(3, 3, 3, 6) ~ 138, R(3, 3, 3, 7) 2: 194, R(3, 3, 4, 4) ~ 114; R(4,19) ~ 194, R(4,20) 2: 230, R(4,21) ~ 242, R(5,17) ~ 282, R(5,19) 2: 338, R(6, 17) ~ 500, R(7, 17) 2: 548. 1 Circulant graphs of prime order For a given prime integer p = 2m+l, let Zp {-m,···, -1,0,1, ... , m} = [-m, m]. (For s ~ t, we denote the set {8, 8 + 1"", t} by [8, t].) In the rest of the paper, unless the contrary is implied, all integers will be considered to be members of Zp,