学位论文 > 优秀研究生学位论文题录展示

Ramsey数的上界研究

作　者: 牟丽英
导　师: 李赵祥
学　校: 中央民族大学
专　业: 基础数学
关键词: Ramsey定理 Ramsey数抽屉原理 sum-free set 循环图
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 39次
引　用: 0次
阅　读: 论文下载

内容摘要

自1928年Ramsey提出了著名的Ramsey定理之后,引起了对Ramsey类型问题的广泛研究.Ramsey数是其中一个非常重要的问题,但是Ramsey数的研究进展非常缓慢。人们应用各种各样的方法也只得到了Ramsey数有限的几个值.所以Ramsey数成为了组合数学、离散数学、图论、算法研究领域的著名难题和热门课题.学者们都试图找到求Ramsey数的一个通用方法,而不是一个一个的求出Ramsey数的值,但是到目前为止,仍然没有找到一种合理的方法来求出Ramsey的所有值.本文一共采用了三种方法来求不同类型的Ramsey数的上界.第一种方法是：抽屉原理.利用抽屉原理证明了Erdos和Szekeres(1935)以及Greenwood和Gleason(1955)提出的Ramsey数定理及其推广,同时由抽屉原理还得到了两类Ramsey的上界公式：Rn-1(k;k+1)≤n(Rn(k)-1)+2与Rn-1(k;l+1)≤n(Rn-1(k;l)-1)+2.第二种方法是：将整数集合的S-F-S分拆进行推广,并对其进行了仔细的研究,然后说明其在求Ramsey数R(3,q)上界中的作用.第三种方法是：循环图.应用循环图求经典多色Ramsey数Rn-1(3；q)的上、下界.首先提出了计算Ramsey数Rn-1(3；q)下界的一种方法,然后根据根据这种方法得到了计算Ramsey数Rn-1(3；q)上界的一种新方法,并利用所提出的方法得到了R(3,3,4)=30.

全文目录

摘要  2-3
ABSTRACT  3-7
第一章绪论  7-10
  1.1 RAMSEY数研究的理论背景  7-8
  1.2 RAMSEY数的研究意义  8-9
  1.3 论文的组织结构  9-10
第二章 RAMSEY数  10-15
  2.1 图的基本知识  10-11
  2.2 RAMSEY数的概念及基本性质  11-12
  2.3 RAMSEY数的研究现状  12-13
  2.4 本文的主要贡献  13-14
  2.5 小结  14-15
第三章抽屉原理与RAMSEY数的上界  15-21
  3.1 抽屉原理  15-18
    3.1.1 抽屉原理的定义  15-16
    3.1.2 抽屉原理应用  16-18
  3.2 RAMSEY数的相关定理的抽屉原理证明  18-19
  3.3 两类RMASEY数的上界  19-20
  3.4 小结  20-21
第四章整数集合的SUM-FREE集分拆的研究  21-29
  4.1 sum-free集分拆的概念与性质  21-22
  4.2 sum-free集分拆的推广  22-23
  4.3 φ(n,k)的性质  23-26
  4.4 ψ(n,k)的性质  26-27
  4.5 g(n,k)与ψ(n,k)的应用  27-29
第五章循环图与RAMSEY数的上、下界  29-40
  5.1 循环图的概念与性质研究  29-30
  5.2 求Ramsey数下界的一种算法  30-33
    5.2.1 循环图的构造  30-31
    5.2.2 用循环图求Ramsey数R_(n-1)(3;q)下界  31-33
  5.3 RAMSEY数上界的计算方法  33-39
  5.4 小结  39-40
第六章总结与展望  40-42
  6.1 总结  40
  6.2 展望  40-41
  6.3 本文的不足  41-42
参考文献  42-44
攻读学位期间发表的学术论文  44-45
致谢  45-46

相似论文

Ramsey理论中的构造与随机图方法,O157.5
距离图的着色和循环图的星极性,O157.5
最大频繁子图挖掘算法研究,TP301.6
一些广义Ramsey数计算,O157.5
基于系统视角的能源效率反弹效应研究,F206
赋权图的DNA计算模型,O157.5
广义Petersen图和循环图的罗马支配研究,O157.5
循环图和广义Petersen图的支配参数,O157.5
步长为1和k的循环图的导出匹配可扩性,O157.5
图的电阻距离和Kirchhoff指标,O157.5
制造执行系统中生产作业计划与调度技术研究,TH165
三正则图及其相关图的交叉数问题,O157.5
Some Upper Bounds of Ramsey Functions,O157.5
竞赛数学中的Ramsey型问题,O157
不含偶圈C_（2m）的r色Ramsey数R_r（C_（2m））的下界,TP301
经典Ramsey理论及其应用,O157.5
若干类图支配问题的研究,O157.5
若干图的Ramsey数研究,TP301.6
图的交叉数等图论难题的研究,O157.5
Ramsey理论中图的构造与计算,O157.5