有限随机结构和若干Ramsey型问题

A finite structure is a finite set V together with a subset of the power set of V. A Ramsey-type problem is the one to consider the relation between the scale of a finite structure and the existence of some sub-structure. In this project, we will consider how large a monochromatic subset of V can be contained in a finite structure without some given sub-structure, calculate some Ramsey numbers concerning graphs or hypographs and some related parameters of graphs. This is one of the most active and important research fields in extremal combinatorics. The main goal of this project is to consider the conjecture of Erdős and Hajnal on the monochromatic subset in a graph containing no some given induced subgraph, estimate the scale of a monochromatic subset in a given 3-uniform hypographs, investigate the Ramsey functions R(C4,Km) and R(C4,K1,n), and some related parameters of graphs.

有限结构指一个有限集及其幂集的一个子集合。Ramsey-型问题是指有限结构的规模与其是否包含某些子结构之间的关系。本项目拟研究在某些禁用子结构的条件下有限结构中单色子集的大小，以及一些图或超图Ramsey数和若干相关图参数，目前是极值组合中最活跃最重要的研究领域之一。主要内容是Erdős和Hajnal关于图中不含诱导子图H时单色子集(完全图或独立集)大小的猜想、3-一致超图中单色子集大小的估计、图Ramsey数R(C4,Km)和R(C4,K1,n)及相关的一些图参数。

确定了当 X 与 Y 是随机图时，保证 friends-and-strangers 图 FS(X,Y) 连通的概率阈值，一般性的拓展了Alon, Defant 和 Kravitz 的结论；系统的研究了四圈-星经典 Ramsey 数及其相关问题，得到了一系列上下界和准确值；利用图的泛圈性质以及图与补图之间固定长度圈的相互制约关系，完全证明了Hansson 关于两个圈集合 Ramsey 数的猜想。该结论对经典圈-圈 Ramsey数给出了一个统一简洁的证明；完全确定了所有圈的 Gallai Ramsey数, 部分确定了 3-一致超图中路对星的Ramsey数；确定了关于一般线性森林的广义Turán数的值和相应的极图，一般化了很多关于线性森林经典Turán数的结果，同时几乎证明了袁龙图和张晓东关于线性森林经典Turán数的猜想；确定了所有n阶极大外可平面图最好可能的定向直径，证明了Surmacs的猜想；证明了任何直径为3的2-边连通图，其最优定向直径是 9. 这是自1978年直径为2的2-边连通图最优定向直径确定40余年之后，第二个确定的最优定向直径；利用经典的最长圈分析方法给出了k-连通图中每个最长圈都是控制圈的最好可能的度和条件，该结论是Bondy关于2-连通图以及陆玫等关于3-连通图相应结论的一般化；证明了陈冠涛等人关于Broom生成树存在性的度和条件猜想；建立了图的孤立韧度和路径因子消去图、分数临界图之间的联系。