图的Ramsey数及相关极图问题的研究

摘要

图论是离散数学的一个重要分支，而Ramsey理论是图论研究中的一个重要方向，它已渗透到数学、计算机科学、信息论以及经济金融等领域。求解图的Ramsey数是Ramsey理论研究中的一个很活跃的分支，它在逻辑分析、复杂结构、并行计算和计算几何等计算机科学领域都有重要作用，吸引了国内外许多学者进行研究。
　　极图理论是图论中的一个重要组成部分，它是在Turán极图问题的基础上发展起来的，主要研究顶点数一定且不包含某些子图的图的最大边数，即给定一个图集ψ={H1，H2，…，Hm}，Turán数ex（n;ψ）是顶点数为n且不包含子图Hi(1≤i≤m)的图的最大边数，EX(n;ψ)表示这些边数为ex（n;ψ)的图集。因为Turán数是可着色方案中单色子图可以达到的最大边数，所以极图问题的研究可以确定相关多色Ramsey数的上界。
　　随机图理论是目前图论研究中比较热门的方向之一，它是由Erd(o)s和Rényi建立起来的，他们发现概率方法在解决图论中的某些极问题时非常有用。随机图Ramsey理论研究的一个重要方向是求解某些Ramsey性质的临界函数。OnlineRamsey游戏是随机图Ramsey理论研究的重要内容，其研究成果可以为经典图论中Ramsey数的求解提供参考。
　　本文利用计算机构造与数学证明相结合的方法，对与圈相关的Ramsey数、相关极图问题和圈的非对称online Ramsey游戏问题进行了研究。主要成果如下:
　　对二部Ramsey数b(C2m;C2n)的研究。首先通过给出完全二部图Km+n-2,m+n-2和K2m-1,2m-1对于(C2m，C2n)可2-着色的方案，证明了二部Ramsey数b(C2m; C2n)的下界。在对b(C2m;C2n)上界的证明中，由归纳假设可知第一色子图中存在圈C2m-2。对于b(C2m; K2,2)上界的证明，通过分析不在C2m-2上的4个顶点与其他顶点的邻接情况证明了当m≥4时b(C2m;K2,2)=m+1。而对于b(C2m;C6)上界的证明，由于不在C2m-2上的顶点有6个，所以证明的难度大大增加。通过对8种情形的详细分析最终证明了当m≥4时b(C2m;C6)=m+2。
　　对四色Ramsey数R（C6，H1，H2，H3）的研究，其中H1，H2和H3分别为C4或者C6。首先通过给出K18和K17对于（C6，H1，H2，H3）可4-着色的方案确定了R(C6，C4，C4，C4)≥19，R(C6，C6，C4，C4)≥18和R(C6，C6，C6, C4)≥18。并结合19和20个顶点不含C4或者C6的极图成果确定了R(C6，C4，C4，C4)=19和R(C6，C6，C，C4)≤20。在对R4(C6)和R(C6，C6，C6，C4)上界的证明中，提出了关于两个图的顶点集合之间好的双射的概念。并利用20个顶点不含C6的两个极图的特点，用数学方法证明了这两个极图的顶点之间不存在好的双射，即他们是不可拼接图，从而得到R4(C6)≤20和R(C6，C6，C6，C4)≤20。然后研制了图的拼接算法和对图的边进行两着色的算法进一步对R(C6，C6，H1，H2)的上界进行了改进，最终得到如下结果:R(C6，C4，C4，C4)=19，18≤R(C6，C6,C4,C4)≤19,18≤R(C6,C6,C6,C4)≤19和18≤R4(C6)≤19。
　　对与圈相关的Turán数的研究。首先提出了一种基于MapReduce的分布式极图构造算法，并通过合理映射键值对、平均分割数据集和避免过多的I/O读写等措施提高了算法的执行效率。利用该算法，构造了不超过28个顶点不含C6的所有极图。试验结果表明，与串行算法相比，分布式算法的平均效率达到了75.48％。然后通过对不含C6极图结构的分析，提出了一种在不含C2k的基础图上扩展边以构造顶点较多的不含C2k极图的方法，从而给出了ex（n;{C2k}）的下界。最后，对围长为9的极图EX(n;{C3，C4，…，C8})进行了研究。基于三个围长不小于9的图，给出了n≤57时ex(n;{C3，C4,…，C8}）的下界。通过对围长为9的极图结构的研究，揭示了该类图中集合Dk（即度为k的所有顶点的集合）中顶点的邻接情形与其最大度之间的关系。利用上述关系，用数学方法证明了n=13，16，18，22，26时EX(n;{C3，C4，…，C8})中图的结构，并利用这些图确定了当23≤n≤30时，ex(n;{C3，C4,…，C8}）的准确值。
　　对与圈相关的非对称online Ramsey游戏的研究。首先利用贪婪策略得到了online Ramsey游戏终止的条件:出现危险图F'。然后用数学归纳法证明了危险图集合中的特殊图(F')*是密度最小的图，即d(F'）≥d(F'）*。为证明该性质先研究了两色的情形，通过分析危险图集中图F2的外部边和顶点的覆盖情况，得到F2转化为（F2）*后图密度的变化规律，证明了d(F2）≥d(F2）*。再将两色的情形推广到r色，将F'的边按层结构进行划分，并采用与两色情形类似的证明策略逐层将F'转化为(F')*，通过对每一层的顶点和边的变化情况及其对图密度的影响的详细分析证明了d(F'）≥d(F'）*。最后利用概率方法得到了与圈相关的r色非对称Ramsey游戏的临界函数N0（S,r,n）的下界，其中S={Ck1，Ck2,…，Gkr}，k1≥k2≥…≥kr。