几类Ramsey数的上界

摘要：

　　本文利用抽屉原理证明了Erd(o)s和Szekeres(1935)以及Greenwood和Gleason(1955)提出的Ramsey定理及其推广.并用抽屉原理构造证明了Rn(3)≤n(Rn-1(3)-1)+2.同时由抽屉原理还得了两类Ramsey的上界公式：Rn-1(k；k+1)≤n(Rn(k)-1)+2与Rn-1(k；l+1)≤n(Rn-1(k；l)-1)+2.后一个公式进一步计算可以得到如下形式为：Rn-1(k；l)≤nl-k(Rn(k)-1)+(nl-k-1)/(n-1)+1(l＞k).

关键词： 数理逻辑 证明论 Ramsey数 上界限 抽屉原理

作者: JI Ting 姬婷 MOU Li-ying 牟丽英

作者单位: College of Science, Central University for Nationalities Beijing 100081 中央民族大学理学院 北京 100081

会议类型: 国内会议

会议名称: 中国运筹学会企业运筹学第四届学术年会

会议地点: 呼和浩特

会议语种:中文

页码: 164-166

在线出版日期: 2009-07-01（万方平台首次上网日期，不代表论文的发表时间）