论文部分内容阅读
[摘要]本文提出约束共存性概念，并证明约束共存极小状态的存在性，以及它与Ramsey定理所描述的极小Ramsey现象的等效性。用数量表示这种等效性，就是：r(p -1,q)=R(p,q)这里2≤p≤q均为整数。
由此，我们得到相邻Ramsey数之间的一些基本的序关系，如：R（p,q）≥R（p -1,q+1），R(p -1,q)+R（p,q -1）-R(p -1,q -1) ≤R(p,q)，这里3≤p≤q均为整数。等等。
[关键词]Ramsey现象 Ramsey数 约束共存极小性
上世纪20年代末，一位英国逻辑学家Frank Ramsey建立如下著名的理论[1，2，3]：
Ramsey定理：对于任意给定的正整数t和p1，p2，…，pk≥t，存在一个正整数n，使得对n元集合的所有()个t元集任意划分为k个集合：X1，X2，…，Xk，则总存在一个集合Xi(1≤i≤k)其中含有Pi个元素的所有t元集。称正整数n具有参数（p1，p2，…，pk；t）Ramsey性质，最小的这样的整数n则称Ramsey数，记为：
Rt（p1，p2，…，pk）
特别地，当t=2时，Ramsey数常记为R（p1，p2，…，pk）。
Ramsey理论在计算机、通迅和信息科学等领域有重要的应用前景[1，2]。
到目前为止，关于Ramsey数的准确值仅探明9个[1，3]，许多基本问题还不十分清楚，如对已知的Ramsey数甚至还不能从理论上解释清楚为什么R（3，5） 本文即从Ramsey数的定义着手，以“约束共存”思想，提出了另一個等价的Ramsey数定义，它本质地刻画了R（p1，p2，…，pk）数中各个量之间相互制约关系。
首先，我们引入约束共存的概念。
定义 设2≤p1≤p2≤…≤pk，k≥2为一组整数，若存在正整数n，使得用k种颜色：c1，c2，…，ck对完全图Kn的任意边着色（每边着一色），在不出现c1色完全子图Kp1，c2色完全子图Kp2，…，ck色完全子图Kpk+1限制下，c1色完全子图Kp1-1，c2色完全子图Kp2-1，…，ck-1色完全子图Kpk-1-1，ck色完全子图Kpk必然共存，则称n具有参数（p1-1，p2-1，…pk-1-1，pk）的约束共存性质。最小的这样的整数n则简记为r（p1-1，p2-1，…，pk-1-1，pk）。
例1．r（1，5）=5；r（2，3）=6而5不具有2，3约束共存性质，尽管红色K2，蓝色K3可以同时出现于K5但不是必然出现。
一般地，定义中的正整数n的存在性及其极大、小存在性均可由Ramsey定理及Ramsey数的存在性保证。我们仅陈述有关结果（各定理的证明另文发表）。
关于约束共存极小态和相应的Ramsey现象之间的联系：即Ramsey数与约束共存最小数实际上是同一事物的不同刻画。这就是
定理1.设2≤p 1≤p 2≤…≤pk为一组整数，则
r（p1-1，p2-1，…，pk-1-1，pk）= R（p1，p2，…，pk）（1）
这个定理除了表明：约束共存极小态就是出现相应的Ramsey现象的起始态的这个事实之外，同时，另一方面还表明Ramsey数（或约束共存极小数）中较小参数的改变对Ramsey数值大小影响比其它较大参数要敏感。
例2．r=(2，7)=R(3，7)，r(2，2，3)=R（3，3，3）=17[1，3]。
推论：设2≤p1≤p2≤…≤pk为一组整数，则正整数n具有参数（p1-1，p2-1，…，pk-1-1，pk）约束共存性质的充分必要条件是边k色完全图Kn在不出现c1色完全子图Kp1，c2色完全子图Kp2，…，ck-1色完全子图Kpk-1，ck色完全子图Kpk+1限制下，必然出现ck色完全子图Kpk。
该推论给出了约束共存的一个等价条件：最大参数的约束存在性。
对于一般图Ramsey数[1，2，3]也有类似于定理1的结果。进一步，可以得到相邻各Ramsey数之间基本的大小关系。
定理2. R（p,q）≥R（p-1,q+1） （2）
这里3≤p≤q为整数。
例3．由（2）式：R（7，10）≥R（6，11）≥253，则将R（7，10）现有的下界232[3]提升为253。等等。
尽管Ramsey数很难求得，然而有趣的是利用上述定理我们却可以比较它们的大小。下面是另一个非常有趣的现象或性质：
定理3. r(p,p)= r(p-1,p+1)，2≤p（3）
这个定理表明：Kp-1，Kp+1约束共存极小态，实际上，也是Kp，Kp约束共存极小态。
现在给出Ramsey数网络中对角线以上平行四边形的四个顶点表示的约束共存极小值的关系：如
定理4.设3≤p≤q整数，则Ramsey数网络中四个相邻的Ramsey数之间有如下约束关系：
R(p-1,q)+R（p,q-1）≤R(p,q) + R(p-1,q-1) （4）
R(p,q) ≥R（p,q-1）+ R(p-1,q+1)- R(p-1,q)（5）等等。
例4． 由（5）式，得R（4，8）≥R（4，7）+ R（3，9）-R（3，8）≥57，则R（4，8）现有的下界56[3]提升为57。
上述结论均可平行地推广到一般图以及多参数的情形。
参考文献
[1]张先迪，李正良.图论及其应用[M]，北京：高等教育出版社，2005
[2]Yusheng Li.The Shannon capacity of a communication channel,Ramsey number of graph and a conjecture of Erdos[J],Chinese Science Bulletin ,2001,V46(24):p2025—2028
由此，我们得到相邻Ramsey数之间的一些基本的序关系，如：R（p,q）≥R（p -1,q+1），R(p -1,q)+R（p,q -1）-R(p -1,q -1) ≤R(p,q)，这里3≤p≤q均为整数。等等。
[关键词]Ramsey现象 Ramsey数 约束共存极小性
上世纪20年代末，一位英国逻辑学家Frank Ramsey建立如下著名的理论[1，2，3]：
Ramsey定理：对于任意给定的正整数t和p1，p2，…，pk≥t，存在一个正整数n，使得对n元集合的所有()个t元集任意划分为k个集合：X1，X2，…，Xk，则总存在一个集合Xi(1≤i≤k)其中含有Pi个元素的所有t元集。称正整数n具有参数（p1，p2，…，pk；t）Ramsey性质，最小的这样的整数n则称Ramsey数，记为：
Rt（p1，p2，…，pk）
特别地，当t=2时，Ramsey数常记为R（p1，p2，…，pk）。
Ramsey理论在计算机、通迅和信息科学等领域有重要的应用前景[1，2]。
到目前为止，关于Ramsey数的准确值仅探明9个[1，3]，许多基本问题还不十分清楚，如对已知的Ramsey数甚至还不能从理论上解释清楚为什么R（3，5）
首先，我们引入约束共存的概念。
定义 设2≤p1≤p2≤…≤pk，k≥2为一组整数，若存在正整数n，使得用k种颜色：c1，c2，…，ck对完全图Kn的任意边着色（每边着一色），在不出现c1色完全子图Kp1，c2色完全子图Kp2，…，ck色完全子图Kpk+1限制下，c1色完全子图Kp1-1，c2色完全子图Kp2-1，…，ck-1色完全子图Kpk-1-1，ck色完全子图Kpk必然共存，则称n具有参数（p1-1，p2-1，…pk-1-1，pk）的约束共存性质。最小的这样的整数n则简记为r（p1-1，p2-1，…，pk-1-1，pk）。
例1．r（1，5）=5；r（2，3）=6而5不具有2，3约束共存性质，尽管红色K2，蓝色K3可以同时出现于K5但不是必然出现。
一般地，定义中的正整数n的存在性及其极大、小存在性均可由Ramsey定理及Ramsey数的存在性保证。我们仅陈述有关结果（各定理的证明另文发表）。
关于约束共存极小态和相应的Ramsey现象之间的联系：即Ramsey数与约束共存最小数实际上是同一事物的不同刻画。这就是
定理1.设2≤p 1≤p 2≤…≤pk为一组整数，则
r（p1-1，p2-1，…，pk-1-1，pk）= R（p1，p2，…，pk）（1）
这个定理除了表明：约束共存极小态就是出现相应的Ramsey现象的起始态的这个事实之外，同时，另一方面还表明Ramsey数（或约束共存极小数）中较小参数的改变对Ramsey数值大小影响比其它较大参数要敏感。
例2．r=(2，7)=R(3，7)，r(2，2，3)=R（3，3，3）=17[1，3]。
推论：设2≤p1≤p2≤…≤pk为一组整数，则正整数n具有参数（p1-1，p2-1，…，pk-1-1，pk）约束共存性质的充分必要条件是边k色完全图Kn在不出现c1色完全子图Kp1，c2色完全子图Kp2，…，ck-1色完全子图Kpk-1，ck色完全子图Kpk+1限制下，必然出现ck色完全子图Kpk。
该推论给出了约束共存的一个等价条件：最大参数的约束存在性。
对于一般图Ramsey数[1，2，3]也有类似于定理1的结果。进一步，可以得到相邻各Ramsey数之间基本的大小关系。
定理2. R（p,q）≥R（p-1,q+1） （2）
这里3≤p≤q为整数。
例3．由（2）式：R（7，10）≥R（6，11）≥253，则将R（7，10）现有的下界232[3]提升为253。等等。
尽管Ramsey数很难求得，然而有趣的是利用上述定理我们却可以比较它们的大小。下面是另一个非常有趣的现象或性质：
定理3. r(p,p)= r(p-1,p+1)，2≤p（3）
这个定理表明：Kp-1，Kp+1约束共存极小态，实际上，也是Kp，Kp约束共存极小态。
现在给出Ramsey数网络中对角线以上平行四边形的四个顶点表示的约束共存极小值的关系：如
定理4.设3≤p≤q整数，则Ramsey数网络中四个相邻的Ramsey数之间有如下约束关系：
R(p-1,q)+R（p,q-1）≤R(p,q) + R(p-1,q-1) （4）
R(p,q) ≥R（p,q-1）+ R(p-1,q+1)- R(p-1,q)（5）等等。
例4． 由（5）式，得R（4，8）≥R（4，7）+ R（3，9）-R（3，8）≥57，则R（4，8）现有的下界56[3]提升为57。
上述结论均可平行地推广到一般图以及多参数的情形。
参考文献
[1]张先迪，李正良.图论及其应用[M]，北京：高等教育出版社，2005
[2]Yusheng Li.The Shannon capacity of a communication channel,Ramsey number of graph and a conjecture of Erdos[J],Chinese Science Bulletin ,2001,V46(24):p2025—2028