ABSTRACT

Paul Erdös and Noga Alon give a general sense of Ramsey Number Theory. This paper presents a general form of Ramsey Number Theory in the dimensional case and its promotion by using probabilistic methods. The paper shows the lower bound of in the case of with equal probabilistic 2-coloring situation, and shows the lower bound of in the case of k and l distinguishing with equal probabilistic 2-coloring situation. The paper shows the lower bound of in the case of with equal probabilistic 3-coloring situation, and shows the lower bound of in the case of k, l and m distinguishing with equal probabilistic 3-coloring situation. And the paper shows the lower bound of in the case of with equal probabilistic r-coloring situation, and shows the lower bound of in the case of distinguishing with equal probabilistic r-coloring situation. Finally, we also give the corresponding results of the variety of situations with unequal probabilities.

Keywords:Probabilistic Method, High-Dimensional Ramsey Number Theory, Coloring

高维Ramsey数问题

单传辉

北京工业大学应用数理学院，北京

Email: S201306040@emails.bjut.edu.cn

收稿日期：2015年8月22日；录用日期：2015年9月7日；发布日期：2015年9月11日

摘 要

Paul Erdös和Noga Alon等人给出了一般意义的Ramsey数理论，本文通过概率方法给出了高维情况下的Ramsey数理论及其推广的一般形式。给出了等概率2-着色情况：当时的下界结果；当与有区分时的下界结果。给出了等概率3-着色情况：当时的下界结果；当有区分时的下界结果。给出了r-着色情况下：当时的下界结果；当有区分时的下界结果。最后又给出了不等概率时上述各种情况下的相应结果。

关键词 :概率方法，高维Ramsey数理论，着色

1. 引言

在组合数学中，Ramsey定理，又称Ramsey二染色定理，是解决以下的问题：要找这样一个最小的数，使得个人中必定有个人相识或个人互不认识。也可以表述成：

定义1.1 [1] ：Ramsey数：任意给定正整数和后，总存在一个最小整数，使得每个有个顶点的完全图，或者包含有一个有个顶点的图，或者包含一个有个顶点的独立集；其中数称为Ramsey数。我们知道。

关于此类型的Ramsey数有很多的结论，1947年Paul Erdös给出了等概率情况下的的下界问题，对任意的整数，，后一个不等式是Erdös证明的，前一个不等式是Szekeres给出的。而且Erdös还给出了一般化的Ramsy定理[2] 。当然，Paul Erdös也给出了一些特殊情况的Ramsey数的下界问题和Ramsey数的推广问题。Joel Spencer(1987)的一本题为“概率方法十讲”的专著，精辟地概述了概率方法对Ramsey理论的应用，给出了不等概率情况下的的下界问题[3] 。NogaAlon也做了许多类似的关于的工作。本文想通过用概率方法来考虑关于高维Ramsey数的各类问题及其推广。下面简单地介绍一下概率方法和的概念。

定义1.2 [4] ：概率方法：也称为非构造性方法，它是用来证明一类事物的某些元素具有一定的特性，而无需实际构造那些元素的方法。在一些概率空间，这些元素存在的概率是大于零的。概率方法研究的组合对象和组合结构很有实际意义，例如著名的四色问题，棋盘的完全覆盖问题等很有实用价值。概率方法在解决许多组合数学问题中是一个强有力的工具，许多棘手的问题几乎可以通过运用这种方法的基本知识解决。

定义1.3 [5] ：完全-顶点-一致超平面：我们考虑顶点集合为，子集是一个维数为的面，维数为的面(face)简称为-面，故-面有个元素。完全-顶点-一致超平面(the complete n-vertex d-uniform hypergraph)是指的顶点集合上所有-面的集合， -面也称为完全-顶点-一致超平面的超边(hyperedges)。

定义1.4 [5] ：高维Ramsey数：是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面(the complete n-vertex d-uniform hypergraph)的超边(hyperedges)着红色/蓝色，或者包含一个完全的-顶点红色超图(a complete l-vertex red hypergraph)或者包含一个完全的-顶点蓝色超图(a complete k-vertex blue hypergraph)。完全-顶点-一致超平面有个超边。当时，完全-顶点-一致超平面就是我们传统意义上的完全图，问题也就是传统意义上的Ramsey数问题。

2. 等概率着色下的高维Ramsey数

2.1. 等概率2-着色情况下的问题

现在考虑时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么它的完全的 -顶点超图满足的结论是：

定理2.1

证明：我们设事件表示任意完全的-顶点超图没有单色的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是单色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是单色，要么都是红色，要么都是蓝色，而取红色或蓝色的概率都是，所以，而完全的-顶点超图是单色的总共又有个，所以：

上式，故：

又由：

我们让，即让，也即;所以时，成立，此时：

也成立，故此时成立，事件存在，即任意完全的-顶点超图没有单色的情况存在，所以。证毕。

我们现在再考虑一般的情形，即与有区分时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么满足的结论是：

定理2.2如果，则。

证明：是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着红色/蓝色，或者包含一个完全的-顶点红色超图或者包含一个完全的-顶点蓝色超图。完全-顶点-一致超平面有个超边。我们设事件表示任意完全的-顶点超图不是红色或者任意完全的-顶点超图不是蓝色的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是红色的且至少有一个完全的-顶点超图是蓝色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是红色，而取红色的概率为，所以；同理完全的-顶点超图有条超边，要让这些超边都是蓝色，而取蓝色的概率都是，所以，而完全的-顶点超图是红色又有个和完全的-顶点超图是蓝色的又有个，所以：

上式，故：

又由已知条件知：

所以：

故此时成立，事件存在，即任意完全的-顶点超图不是红色或者任意完全的-顶点超图不是蓝色的情况存在，所以。证毕。

2.2. 等概率3-着色情况下的问题

上面说的是2-着色时的，现在我们来考虑3-着色相应的情形，此时，对于有以下结论成立。是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1、颜色2和颜色3，或者包含一个完全的-顶点颜色1的超图或者包含一个完全的-顶点颜色2的超图或者包含一个完全的-顶点颜色3的超图。

现在考虑时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么它的完全的-顶点超图满足的结论是：

定理2.3

证明：我们设事件表示任意完全的-顶点超图没有单色的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的 -顶点超图是单色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是单色，要么都是颜色1，要么都是颜色2，要么都是颜色3，而取颜色1或者颜色2或者颜色3的概率都是，所以，而完全的-顶点超图是单色的总共又有个，所以：

上式，故：

又由：

我们让，即让，也即；所以时，成立，此时：

也成立，故此时成立，事件存在，即任意完全的-顶点超图没有单色的情况存在，所以。证毕。

我们现在再考虑一般的情形，即有区分时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么满足的结论是：

定理2.4 如果，则。

证明：是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1、颜色2和颜色3，或者包含一个完全的-顶点颜色1的超图或者包含一个完全的-顶点颜色2的超图或者包含一个完全的-顶点颜色3的超图。完全-顶点-一致超平面有个超边。我们设事件表示任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是颜色2或者任意完全的-顶点超图不是颜色3的情况，事件X若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件X的补事件，表示至少有一个完全的-顶点超图是颜色1的且至少有一个完全的-顶点超图是颜色2的且至少有一个完全的-顶点超图是颜色3的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是颜色1，而取颜色1的概率为，所以；同理完全的-顶点超图有条超边，要让这些超边都是颜色2，而取颜色2的概率是,所以；完全的-顶点超图有条超边，要让这些超边都是颜色3，而取颜色3的概率是，所以。而完全的-顶点超图是颜色1又有个，完全的-顶点超图是颜色2的又有个和完全的-顶点超图是颜色3的又有，所以：

上式，故：

又由已知条件知：

所以：

故此时成立，事件存在，即任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是颜色2或者任意完全的-顶点超图不是颜色3的情况存在，所以。证毕。

2.3. 等概率r-着色情况下的问题

现在我们来考虑r-着色相应的情形，此时，对于有以下结论成立。是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1，颜色2，,颜色r，或者包含一个完全的-顶点颜色1的超图或者包含一个完全的-顶点颜色2的超图，，或者包含一个完全的-顶点颜色r的超图。

现在考虑时的 (有个)的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么它的完全的-顶点超图满足的结论是：

定理2.5。

证明：我们设事件表示任意完全的-顶点超图没有单色的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是单色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是单色，要么都是颜色1，要么都是颜色2，，要么都是颜色r，而取颜色1或者颜色2，，或颜色r的概率都是，所以，而完全的-顶点超图是单色的总共又有个，所以：

上式，故：

又由：

我们让，即让，也即；所以时，成立，此时：

也成立，故此时成立，事件存在，即任意完全的-顶点超图没有单色的情况存在，所以。证毕。

我们现在再考虑一般的情形，即有区分时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么满足的结论是：

定理2.6 如果，则。

证明：是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1，颜色2，，颜色r，或者包含一个完全的-顶点颜色1的超图，或者包含一个完全的-顶点颜色2的超图，，或者包含一个完全的-顶点颜色r的超图。完全-顶点-一致超平面有

个超边。我们设事件表示任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是

颜色2，，或者任意完全的-顶点超图不是颜色r的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是颜色1的且至少有一个完全的-顶点超图是颜色2的，，且至少有一个完全的-顶点超图是颜色r的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是颜色1，而取颜色1的概率为，所以；同理完全的-顶点超图有条超边，要让这些超边都是颜色2，而取颜色2的概率是，所以；；完全的-顶点超图有条超边，要让这些超边都是颜色r，而取颜色r的概率是，所以。而完全的-顶点超图是颜色1又有个，完全的-顶点超图是颜色2的又有个，，完全的-顶点超图是颜色r的又有，所以：

上式，故：

又由已知条件知：

所以：

故此时成立，事件存在，即任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是颜色2，，或者任意完全的-顶点超图不是颜色r的情况存在，所以。证毕。

3. 不等概率着色下的高维Ramsey数

3.1. 不等概率2-着色情况下的问题

上面都是等概率情况下的情形，下面让我们看看不等概率的情形。

现在考虑时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么它的完全的-顶点超图满足的结论是：

定理3.1。

证明：我们设事件表示任意完全的-顶点超图没有单色的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是单色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是单色，要么都是红色，要么都是蓝色，而取红色的概率为，取蓝色的概率为，所以，而完全的k-顶点超图是单色的总共又有个，所以：

上式，故：

又由：

我们让，即让，也即；所以时，成立，此时：

也成立，故此时成立，事件存在，即任意完全的-顶点超图没有单色的情况存在，所以。证毕。

我们现在再考虑一般的情形，即与有区分时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么满足的结论是：

定理3.2如果，则。

证明：是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着红色/蓝色，或者包含一个完全的-顶点红色超图或者包含一个完全的-顶点蓝色超图。完全-顶点-一致超平面有个超边。我们设事件表示任意完全的-顶点超图不是红色或者任意完全的-顶点超图不是蓝色的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的

取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是红色的且至少有一个完全的-顶点超图是蓝色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是红色，而取红色的概率为，所以；同理完全的-顶点超图有条超边，要让这些超边都是蓝色，而取蓝色的概率都是，所以，而完全的-顶点超图是红色又有个和完全的-顶点超图是蓝色的又有个，所以：

上式，故：

又由已知条件知：

所以：

故此时成立，事件存在，即任意完全的-顶点超图不是红色或者任意完全的-顶点超图不是蓝色的情况存在，所以。证毕。

3.2.不等概率3-着色情况下的问题

上面说的是2-着色时的，现在我们来考虑3-着色相应的情形，此时，对于有以下结论成立。是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1、颜色2和颜色3，或者包含一个完全的-顶点颜色1的超图或者包含一个完全的-顶点颜色2的超图或者包含一个完全的-顶点颜色3的超图。

现在考虑时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么它的完全的-顶点超图满足的结论是：

定理3.3。

证明：我们设事件表示任意完全的-顶点超图没有单色的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是单色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是单色，要么都是颜色1，要么都是颜色2，要么都是颜色3，而取颜色1的概率为，取颜色2的概率为，取颜色3的概率为，所以，而完全的-顶点超图是单色的总共又有个，所以：

上式，故：

又由：

我们让，即让，也即；所以时，成立，此时：

也成立，故此时成立，事件存在，即任意完全的-顶点超图没有单色的情况存在，所以。证毕。

我们现在再考虑一般的情形，即有区分时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么满足的结论是：

定理3.4 如果，则。

证明：是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1、颜色2和颜色3，或者包含一个完全的-顶点颜色1的超图或者包含一个完全的-顶点颜

色2的超图或者包含一个完全的-顶点颜色3的超图。完全-顶点-一致超平面有个超边。我

们设事件表示任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是颜色2或者任意完全的-顶点超图不是颜色3的情况，事件若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件的补事件，表示至少有一个完全的-顶点超图是颜色1的且至少有一个完全的-顶点超图是颜色2的且至少有一个完全的-顶点超图是颜色3的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是颜色1，而取颜色1的概率为，所以；同理完全的-顶点超图有条超边，要让这些超边都是颜色2，而取颜色2的概率是，所以；完全的-顶点超图有条超边，要让这些超边都是颜色3，而取颜色3的概率是，所以。而完全的-顶点超图是颜色1又有个，完全的-顶点超图是颜色2的又有个和完全的-顶点超图是颜色3的又有，所以：

上式，故：

又由已知条件知：

所以：

故此时成立，事件存在，即任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是颜色2或者任意完全的-顶点超图不是颜色3的情况存在，所以。证毕。

3.3.不等概率r-着色情况下的问题

现在我们来考虑r-着色相应的情形，此时，对于有以下结论成立。是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1，颜色2，,颜色r，或者包含一个完全的-顶点颜色1的超图或者包含一个完全的-顶点颜色2的超图，，或者包含一个完全的-顶点颜色r的超图。

现考虑时的 (有个)的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么它的完全的-顶点超图满足的结论是：

定理3.5。

证明：我们设事件X表示任意完全的-顶点超图没有单色的情况，事件X若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件X的补事件，表示至少有一个完全的-顶点超图是单色的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是单色，要么都是颜色1，要么都是颜色2，，要么都是颜色r，而取颜色1的概率为，取颜色2的概率为，，取颜色r的概率为，所以，而完全的-顶点超图是单色的总共又有个，所以：

上式，故：

又由：

我们让，即让，也即；所以时，成立，

此时：

也成立，故此时成立，事件X存在，即任意完全的-顶点超图没有单色的情况存在，所以。证毕。

我们现在再考虑一般的情形，即有区分时的的存在性的取值问题。我们考虑完全-顶点-一致超平面，它有个超边，那么满足的结论是：

定理3.6 如果，则。

证明：是这样的最小整数，对于有以下结论成立。给完全-顶点-一致超平面的超边着颜色1，颜色2，，颜色r，或者包含一个完全的-顶点颜色1的超图或者包含一个完全的-顶点颜色2的超图，，或者包含一个完全的-顶点颜色r的超图。完全-顶点-一致超平面有个超边。我们设事件 表示任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是颜色2， ，或者任意完全的-顶点超图不是颜色r的情况，事件X若是存在的话，那么我们最终要求的必然要大于我们求出的的取值要求。我们继续考虑事件X的补事件，表示至少有一个完全的-顶点超图是颜色1的且至少有一个完全的-顶点超图是颜色2的，，且至少有一个完全的-顶点超图是颜色r的情况，则：

而完全的-顶点超图有条超边，要让这些超边都是颜色1，而取颜色1的概率为，所以；同理完全的-顶点超图有条超边，要让这些超边都是颜色2，而取颜色2的概率是，所以；；完全的-顶点超图有条超边，要让这些超边都是颜色r，而取颜色r的概率是 ，所以。而完全的-顶点超图是颜色1又有个，完全的-顶点超图是颜色2的又有个，，完全的-顶点超图是颜色r的又有，所以：

上式，故：

又由已知条件知：

所以：

故此时成立，事件存在，即任意完全的-顶点超图不是颜色1或者任意完全的-顶点超图不是颜色2，，或者任意完全的-顶点超图不是颜色r的情况存在，所以。证毕。

致谢

阴东升副教授在本文的选题和本文的方法方面给予了很大的指导和帮助，本人在此表示深深地感激之情。同时也感谢《理论数学》各位老师对本文提出的宝贵建议。

文章引用

单传辉. 高维Ramsey数问题
On High-Dimensional Ramsey Number[J]. 理论数学, 2015, 05(05): 189-206. http://dx.doi.org/10.12677/PM.2015.55028

参考文献 (References)