求Ramsey数最优下界值的递归算法

A Recursive Algorithm for Solving the Optimal Lower Bounds of Ramsey Numbers

要确定每个具体的Ramsey数的数值是相当困难的,至今人们只求出了为数很少的几个Ramsey数的数值.人们在研究Ramsey数性质的同时,也在估计Ramsey数的数值,得出了某些Ramsey数的下界值,但工作进展缓慢.本文提出了一种计算Ramsey数最优下界值的递归算法,该算法利用当今关于Ramsey数的最新结果,能得出Ramsey数的目前最优下界值.1 算法描述不妨将本算法定名为G,参数个数为1个以上(可变化),算法允许递归调用,其输出值为Ramsey数的目前最优下界值.C(k_1,k_2…,k_n)表示以k_1,k_2…,k_n作为输入,通过算法G所得到的输出结果,即C(k_1,k_2…,k_n)表示的是G算出的Ramsey数N(k_1,k_2,…,k_n;2)的目前最优下界值,其中N(k_1,k_2…,k_n;2)的含意与文献[2]中有关含意相同.算法G:

The Ramsey numbers are of great significance in combinatorics. It is very useful and also very difficult to obtain the exact value of any Ramsey number and only a few of them have so far been obtained. During the last few decades, along with the study of the properties of the Ramsey numbers, people tried to estimate them and obtained some of the lower bounds, but the progress was slow. This paper presents a recursive algorithm which makes it possible to obtain the optimal lower bound of each Ramsey number by using the latest results concerning the properties of Ramsey numbers.