| 【中文题名】 | 经典Ramsey理论及其应用 |
| 【英文题名】 | |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2003-9-4 |
| 【中关键词】 | 图,Ramsey数,下界,染色,同构,素数阶循环图 |
| 【英关键词】 | graph,Ramsey number,lower bound,coloring,isomorphism,cyclic graph of prime order, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
本文用构造性方法研究了经典Ramsey数的下界．我们把求双色经典Ramsey数下界的问题，转化为求两个图的满足某些条件的同构导出子图的问题，并把其中所用的构造性方法推广到多色情形．我们的结果改进了常用的不等式r(k，p+q-1)≥r(k，p)+r(k，q)-1．对于多色情形，Abbott通过构造合成图给出了一些关于多色对角Ramsey数下界的不等式，大部分后来被宋恩民推广到了非对角情形．第三章给出了几种新的构造性方法，改进了Abbott和宋恩民的结果．
利用所证明的定理，我们给出了大量Ramsey数的新下界，它们均优于以往文献中的最好结果．其中包括r(4，13)≥133，r(4，14)≥141，r(4，15)≥153，r(6，7)≥111，r(6，11)≥253，r_5(4)≥2328，r_4(6)≥10507，r_4(7)≥42407，r(3，3，10)≥141，r(3，3，11)≥157，r(3，3，3，11)≥561，r_4(5)≥2550，r_5(5)≥26082等．
第四章我们研究了在通讯频道的Shannon容量研究中具有重要意义的r_n(3)的界，讨论了奇圈的补... |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
ABSTRACT |
5-6 |
|
第一章 绪论 |
6-10 |
|
1.1 图论基本知识 |
6-7 |
|
1.2 Ramsey理论的发展简史 |
7-9 |
|
1.3 本文各章内容的安排 |
9-10 |
|
第二章 求Ramsey数r(k，l)下界的一种构造性方法 |
10-18 |
|
2.1 主要定理 |
10-11 |
|
2.2 应用定理求一些Ramsey数的下界 |
11-16 |
|
2.3 结论及简单讨论 |
16-18 |
|
第三章 对多色经典Ramsey数下界的改进 |
18-34 |
|
3.1 引言 |
18 |
|
3.2 关于r(3，k，l) |
18-22 |
|
3.3 主要定理 |
22-31 |
|
3.4 应用定理求一些Ramsey数的下界 |
31-34 |
|
第四章 Ramsey理论与通讯频道的Shannon容量 |
34-40 |
|
4.1 通讯频道的Shannon容量简介 |
34-35 |
|
4.2 Ramsey理论在求通讯频道的Shannon容量中的应用 |
35-36 |
|
4.3 对Ramsey数r_n(3)和Schur数上界的改进 |
36-40 |
|
第五章 讨论与展望 |
40-44 |
|
5.1 Ramsey图的连通性 |
40-41 |
|
5.2 一些猜想 |
41-42 |
|
5.3 一点展望 |
42-44 |
|
致谢 |
44-45 |
|
参考文献 |
45-46 |
|
| 【DOI】 | LunWen.ID:2.2008.11427 |
