若干图的Ramsey数研究

论文摘要

Ramsey理论是离散数学的一个重要分支，而图的Ramsey数研究是Ramsey理论的一个主要研究方向。Ramsey理论在很多领域都有应用，包括：数论，代数，几何学，拓扑学，集合论，逻辑学，信息论和理论计算机科学等。Ramsey数的确定是NP困难的。到目前为止，仅得到少数图的Ramsey数的准确值。计算机技术的应用使图的Ramsey数研究成为当前Ramsey理论研究中最活跃的领域。本文将计算机构造性证明与数学证明相结合，对偶圈C2m的r色Ramsey数Rr(C2m)的下界，圈的三色Ramsey数和图的平面Ramsey数这三个问题进行研究。 1990年，Graham，Rothschild和Spencer在《Ramsey Theory》中证明了：Rr(C2m)≥（r-1）（m-1）+1。本文给出了两种对完全图的r-着色方法，从而证明了Rr(C2m)≥max{（r+1）m-1+（r mod 2），2（r-1）（m-1）+2}。特别地，当r=3时R3(C2m)≥4m。已有的结果R3（C6）=12和本文的结果R3（C8）=16表明：当m=3和4时，等号成立。 当m≤7时，圈的三色Ramsey数R3（Cm）的值已经确定。本文研制了构造不含圈Cm的临界图算法和对一个图的所有边进行两着色的算法。利用这两种算法，证明了R3（C8）=16；对m2≤m1＜m0≤7给出了R(Cm0，Cm1，Cm2)的值。1976年，Erd（?）s等证明了：当m足够大时，R（Cm，C3，C3）=5m-4和R（Cm，C4，C4）=m+2。本文对m不是足够大的情形进行研究，证明了：当m≥5时，R（Cm，C3，C3）=5m-4。利用上述算法，证明了：当m≥11时，R（Cm，C4，C4）=m+2。并证明了：R（Cm，C4，C4）=12（5≤m≤8）和R（Cm，C4，C4）=13（9≤m≤10）。 1969年，Walker首先提出了平面Ramsey数PR（H1，H2）的概念。Bielak和Gorgol证明了PR（C4，K5）=13，PR（C4，K6）=17和PR（C4，Kl）≥3l+「（l-1）／5」-2（l≥3）。本文研制了计算平面Ramsey数PR（H1，H2）的算法。利用这个算法，证明了PR（K4-e，K5）=14，PR（K4-e，K6）=17和PR（C4，K7）=20。对其中的PR（K4-e，K5）=14和PR（C4，K7）=20还给出了数学证明，同时证明了：当l≥3时，PR（K4-e，Kl）≥3l+「（l-1）／4」-2。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 图的Ramsey数
• 1.2 图的平面Ramsey数
• 1.3 理论意义及应用背景
• 1.4 本文工作
• 2m的r色Ramsey数R_r(C_2m)的下界'>2 偶圈C_2m的r色Ramsey数R_r(C_2m)的下界
• 2.1 基本定义与引理
• r(C_2m)的下界'>2.2 利用1-因子分解理论改进R_r(C_2m)的下界
• r(C_2m)（r≥4）下界的进一步改进'>2.3 对R_r(C_2m)（r≥4）下界的进一步改进
• 2.4 小结
• 3 圈的三色Ramsey数
• 3.1 基本引理及算法
• m₀,C_m1,C_m2)（m₂≤m₁＜m₀≤7且（m₁,m₂）≠（3,3））'>3.2 R(C_m0,C_m1,C_m2)（m₂≤m₁＜m₀≤7且（m₁,m₂）≠（3,3））
• 3（C₈）'>3.3 R₃（C₈）
• m,C₃,C₃）'>3.4 R（C_m,C₃,C₃）
• m,C₄,C₄）'>3.5 R（C_m,C₄,C₄）
• 3.6 小结
• 4,K_l）和PR（K₄-e,K_l）'>4 平面Ramsey数PR（C₄,K_l）和PR（K₄-e,K_l）
• 4.1 基本定义与引理
• 4,K_l）（l≤6）和PR（K₄-e,K_l）（l≤7）'>4.2 计算PR（C₄,K_l）（l≤6）和PR（K₄-e,K_l）（l≤7）
• 4-e,K₅）'>4.3 PR（K₄-e,K₅）
• 4,K₇）'>4.4 PR（C₄,K₇）
• 4.5 小结
• 结果与展望
• 参考文献
• 攻读博士学位期间发表学术论文情况
• 创新点摘要
• 致谢
• 大连理工大学学位论文版权使用授权书