局部Ramsey数和局部边染色

Ramsey theory has been a research focus in Combinatorics. It refers to the study of partitions of large structures, which indicates that complete disorder is impossible. Graph Ramsey theory is a major branch of Ramsey theory. A local (mean) k-coloring of a graph is a coloring of the edges such that, the edges incident to each vertex are colored with at most k different colors (on average). Given a graph G, the local (mean) k-Ramsey number is defined as the smallest integer N such that, any local (mean) k-coloring of K_N contains a monochromatic copy of G...This project aims at expanding and deepening the interconnections of generalized Ramsey numbers, local Ramsey numbers and mean Ramsey numbers; studying the necessary and sufficient condition for which a local (H,k) edge coloring is in fact a k-edge-coloring; putting forward some new ideas, broadening the scope of graph Ramsey theory, and finally obtaining some significant breakthroughs.

Ramsey理论一直是组合数学的研究热点。它是对充分大的结构进行划分的研究，印证了完全的无序是不可能的。而图Ramsey理论是Ramsey理论的重要分支。图的局部（平均）k边染色是一种边染色，使得与任意顶点关联的边（平均）至多染k种不同的颜色。图G的局部（平均）k-Ramsey数定义为最小的正整数N，使得N阶完全图的任意局部（平均）k边染色都包含单色图G。..本项目旨在拓展和深化广义Ramsey数、局部Ramsey数和平均Ramsey数之间的内在联系；研究局部(H,k)边染色导出一般边染色的充要条件；提出新的想法，扩展图Ramsey理论的研究内容，力争取得更有意义的突破。

本项目主要开展了广义Ramsey数及其变式的研究。在Ramsey数的准确值方面，我们分别研究了圈-星、圈-书、扇-轮、星-轮、轮-轮的Ramsey数。在与南京大学图论团队的合作中，利用最长圈和弱泛圈技巧，我们扩大了圈-书Ramsey数的一般化结果；利用找圈和找匹配的方法，开启了小扇-大轮Ramsey数的研究；利用了Erdos-Simonovits稳定性定理，对星-轮Ramsey数的未解部分在星充分大时给予解决；综合运用极值图论和图Ramsey理论的多项结论作为引理，将轮-轮Ramsey数的已知值由6个推广为无限多个。同时，课题负责人加入了波兰科学院院士Luczak团队，与Luczak和Polcyn合作，得到了偶圈和星充分大时，偶圈-星Ramsey数的准确值。.在Ramsey数的变式研究方面，利用平面Ramsey数的一些结论和对树的分析，我们得到了全部四圈对树的平面Ramsey数；研究了有关完全图去一条边的诱导Ramsey数，为更多稀疏图的诱导Ramsey数提供方法；初步探究了弱Ramsey数和弱超图Ramsey数，稀疏图中的相关问题还在进一步的探究中。.包括上述结果在内，目前已完成学术论文（包括发表和在投）八篇，总体实现了项目的预期目标。本课题结项后，负责人还将继续开展相关的课题研究。