Ramsey理论彩虹推广的研究

Ramsey theory is one of the most important areas in graph theory, which has important theoretical significance and actual value. During the recent years, the rainbow generalizations of Ramsey theory developed rapidly. The attention from several known graphists, including Alon and Gyarfas, further promoted the study of the rainbow generalizations of Ramsey theory, which has become one.of the front and hot topics in graph theory. In this project, we plan to consider the following problems. (1) Study the anti-Ramsey number of graphs and hypergraphs and characterize the relationship between them and the Turan number. (2) Study the rainbow Ramsey number and Gallai Ramsey number of graphs and hypergraphs, and characterize the relationship between them and the Ramsey number. (3) Study the anti-Ramsey numbers under edge-colorings with constrains and study the generalizations of anti-Ramsey number. (4) Study combinatorial optimization problems in rainbow generalizations of Ramsey theory with its applications. Study several parameters in graph structure, graph coloring and combinatorics. The results of this project will help us better understand the relationship between rainbow generalizations of Ramsey theory and classic Ramsey theory, extremal graph theory and combinatorial design. The development of this project will further enrich and promote the study of Ramsey theory.

Ramsey理论是图论研究最重要的分支之一，具有重要的理论意义和应用价值。Ramsey理论的彩虹推广近年来发展迅速，Alon、Gyarfas等国际权威学者的关注大大推动了该领域的发展，使之成为图论研究的前沿和热点课题之一。本项目旨在以下方面开展研究：（1）研究图和超图的anti-Ramsey数，刻画其与Turan数之间的联系。（2）研究图和超图的彩虹Ramsey数和Gallai Ramsey数，探讨其与经典Ramsey数之间的内在联系。（3）研究局部边染色等限制条件边染色下图和超图的anti-Ramsey数及其推广。（4）研究Ramsey理论彩虹推广中相关的组合最优化问题及其应用，研究图的结构、图的染色及组合数学中的若干参数。本项目研究结果将有助于加深理解Ramsey理论彩虹推广问题与经典Ramsey理论、极值图论及组合设计等分支之间的联系及应用，丰富和推动Ramsey理论的研究。

Ramsey理论是图论研究最重要的分支之一，具有重要的理论意义和应用价值。近十余年来，Ramsey理论的彩虹推广近年来发展迅速，Alon、Gyarfas等国际权威学者的关注大大推动了该领域的发展，使之成为图论研究的前沿和热点课题之一。本项目执行期间项目组研究了匹配anti-Ramsey数的极值边染色，刻画了匹配在完全图中该边染色的唯一性特征；研究了完全分裂图中匹配的anti-Ramsey数，完全确定了其表达公式，这一结论覆盖了此前完全图中匹配的anti-Ramsey数；研究了3-正则二部图中匹配的anti-Ramsey数，改进了Li&Xu的相关结论；研究了平面图中匹配的anti-Ramsey数，得到了其新的上下界，这一结论改进了现有的结论；研究了超图中匹配的anti-Ramsey数问题，确定了完全三部3一致超图中匹配的anti-Ramsey数；研究了限制条件下图的anti-Ramsey问题，确定了不含有单色匹配的边染色条件下团的anti-Ramsey数；研究了Kneser图中3-圈的anti-Ramsey数；寻找给定边染色图中最大彩虹匹配是一个NP问题，给出了一个启发式算法，该算法能够在多项式时间内或者找到一个大的彩虹匹配，或者找到一个包含颜色数相对有限的完全子图；图的彩虹连通性、图的染色方面取得了若干的研究成果。本项目研究结果将有助于丰富和推动Ramsey理论的研究，进一步揭示Ramsey理论彩虹推广问题与经典Ramsey理论、极值图论等分支之间的内在联系。