图的Ramsey理论研究中的构造性方法

Ramsey theory is an important area of combinatorics that is well known for its difficulty. It has numerous important applications in mathematics, and in communication theory, information theory and computer science. Constructive methods in Ramsey theory and its applications aim mainly at designing extremal structures with a delicate trade-offs between competing properties. The research in this project will focus on the constructive methods, together with tools in algebra, number theory, probability theory and analysis, to study in depth the lower bounds for classical Ramsey numbers by studying the relation between different classical Ramsey numbers, study Folkman numbers by studying a Folkman type problem with bounded chromatic numbers,and use these methods to study multigraph Ramsey numbers and local Ramsey numbers. This will very likely lead to new insights and results on Ramsey and Folkman structures and numbers. We anticipate that progress on this project will not only contribute to the knowledge of the constructive Ramsey theory, but also lead to new estimates of the Shannon capacity of noisy channels modeled by graphs, and new knowledge on other related problems in information theory and computer science.

Ramsey理论是组合数学的重要分支，以难度大著称,在许多数学分支及通信理论、信息论和计算机科学中有许多重要应用。Ramsey理论及应用中的构造性方法，主要是为了设计一些兼顾若干矛盾着的性质的极值结构。本项目将主要利用构造性方法，结合代数、数论、概率和分析中的工具,通过深入研究各种经典Ramsey数之间的关系来研究经典Ramsey数的下界，通过研究一个有色数限制的Folkman型问题来研究Folkman数的上界，并将这些方法用于研究多图Ramsey数和local Ramsey数。这将很有希望给出关于Ramsey数和Folkman数及相应结构的更多深刻的认识和结果。我们希望本项目中的进展不仅能为Ramsey理论中构造性方法的发展做出贡献，还能给出图的Shannon容量的新结果，加深我们对信息论和计算机科学中其他问题的认识。

本项目用构造性方法研究图的Ramsey理论中的一些问题，主要研究经典Ramsey数的下界，顶点和边Folkman数的上界等。对于Ramsey数，证明了一些与R(3,s)和R(K_3, K_s-e)有关的结果，利用合成图研究了local Ramsey数，给出了基于twin Ramsey数及其推广的多色经典Ramsey数的下界。我们还研究了Paley图的团数。关于多色对角经典Ramsey数下界的研究，加深了对有独立数限制的图的Shannnon容量的理解。对于Folkman数，证明了顶点色Folkman数的存在性，将一些关于顶点Folkman数的结果推广到广义顶点Folkman数，并给出了一些边Folkman数的新上界。