图的Ramsey理论中的随机方法

图的Ramsey理论所研究的问题既是极值图论研究中的重要问题, 同时也都是一些困难的问题, 其研究对图论的发展有着重要意义. 图的随机方法是在研究极值图论特别是Ramsey理论的研究过程中产生并发展起来的, 该方法可以在不弄清楚图的具体结构的基础上研究目标结构的存在性,其主要是通过构造概率空间, 计算目标组合结构出现的概率实现的. 本项目旨在通过运用随机方法并结合其他一些方法, 如分析方法、代数, 几何方法等研究含某些密集图类的Ramsey数、多色Ramsey数、二部Ramsey数以及广义Ramsey数- - Folkman数等. 另外, 本项目还将讨论Lovasz局部引理.

图的Ramsey理论所研究的许多问题既是极值图论研究中的重要问题,同时也都是一些困难的问题.本项目主要利用随机方法以及代数构造讨论Ramsey数的上下界及相关问题.利用随机方法,我们得到了Ramsey数$r(K_3,K_{n,n})$的渐近准确阶,Kim因为得到Ramsey数$r(K_3,K_n)$的渐近准确阶而获得1997年度Folkerson奖.利用Paley图,我们给出了含$K_1+G$多色Ramsey数的下界,其中图$G$最小度大于1.特别地,在二着色情况下,部分验证了A. Thomason猜想,即$r(K_m+\overline{K_n})=2^mn+o(n)$.关于不含奇圈的独立数的下界,我们得到阶数为$N$的图若不含长为$2m$和$2m+1$的圈, 则该图的独立数大于$\Omega((N\log N)^{m/(m+1)})$.另外,本项目给出了Lovasz局部引理的一个应用,得到若图$G$的围长$g(G)\ge c\frac{\Delta}{r}\log\frac{\Delta^2}{r}$,则无圈边色数$\chi'_a(G)\le \Delta+r+1$.