七种多色Ramsey数的新下界

"这篇论文是关于多色Ramsey数的研究，特别是关注三色和四色Ramsey数的下界。作者通过研究素数阶完全图的循环圈分解方法，提出了计算子图团数的算法，并据此得出了一系列新的下界：R(3,4,18)至少为450，R(3,4,19)至少为464，R(3,4,20)至少为522，R(3,3,5,10)至少为542，R(3,3,5,11)至少为9618，R(3,4,5,16)至少为1410，以及R(3,4,5,17)至少为430。这些结果是在组合数学领域内对Ramsey数理论的重要贡献，Ramsey数是确定在无向图中避免特定结构所需的最小顶点数。" 这篇论文深入探讨了多色Ramsey数的理论，这是一个在图论和组合数学中具有挑战性的问题。Ramsey数R(k_1, k_2, ..., k_t)定义为最小的整数N，使得任何用t种颜色给N个点画边的完全图中，至少包含一个大小为k_1的同色团或一个大小为k_2的同色团，以此类推，直到k_t。在这篇1999年的论文中，研究者特别关注了三色和四色的Ramsey数，并且在素数阶完全图的背景下进行了研究。 他们引入了一个新方法，即通过素数阶完全图的循环圈分解来研究这个问题。具体来说，他们将图的顶点集和边集分别设为Z_p和Z_p的所有2元子集，然后对边进行n-染色，这里的n至少为3。每种颜色代表一种特定的邻接关系，这导致了所谓的“Si色边”。每个Si色边集合对应的导出生成子图Gp(S_i)被定义，其团数Ci是关键的量，因为它们与Ramsey数的下界直接相关。 通过这种方法，作者能够计算出一系列新的多色Ramsey数下界。例如，他们证明了在至少450个顶点的图中，无论如何着色，总能找到一个包含18个顶点的红色、蓝色和黄色的完全子图，或者找到一个包含19个顶点的红色、蓝色和黄色的完全子图，依此类推。这些下界对理解Ramsey数的性质和进一步研究提供了重要的基础。 此外，这篇论文还提到了一些已知的Ramsey数的下界，如R(3,4,4)至少为55，R(3,3,9)至少为90等，以及文献引用中的其他结果。这些比较展示了新下界的改进和对现有知识的扩展。 总而言之，这篇论文在多色Ramsey数的理论框架下，通过创新的图着色方法和团数计算，为研究多色Ramsey数的下界提供了有价值的见解，有助于推动组合数学领域的进展。