报告题目：Packing nearly optimal Ramsey~$R(3,t)$ graphs

报告时间：2019年12月26日， 星期四，上午10：00-11：00、

报告地点：北五楼 427

报告人：郭赫

报告摘要：

In 1995 Kim famously proved the Ramsey bound~$R(3,t) \ge c t^2/\log t$ by constructing an $n$-vertex graph that is triangle-free and has independence number at most~$C \sqrt{n \log n}$.
We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph~$K_n$ into a packing of such nearly optimal Ramsey~$R(3,t)$ graphs.

More precisely, for any $\epsilon>0$ we find an edge-disjoint collection $(G_i)_i$ of $n$-vertex graphs $G_i \subseteq K_n$ such that (a)~each $G_i$ is triangle-free and has independence number at most $C_\epsilon \sqrt{n \log n}$, and (b)~the union of all the $G_i$ contains at least $(1-\epsilon)\binom{n}{2}$ edges.
Our algorithmic proof proceeds by sequentially choosing the graphs~$G_i$ via a semi-random (i.e., R\"{o}dl nibble type) variation of the triangle-free process. 

As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szab\'{o} (concerning a Ramsey-type parameter introduced by Burr, Erd\H{o}s, Lov\'asz in 1976). Namely, denoting by~$s_r(H)$ the smallest minimum degree of $r$-Ramsey minimal graphs for~$H$, we close the existing logarithmic gap for~$H=K_3$ and establish that~$s_r(K_3) = \Theta(r^2 \log r)$.

Based on joint work with Lutz Warnke.

报告人简介：

郭赫2015年本科毕业于浙江大学丘成桐数学班。2014至2015年曾在哈佛大学交流半年。2015起在佐治亚理工学院算法，组合，和优化项目读博士，导师是Lutz Warnke. 主要研究方向是组合中的概率方法，随机图过程，拉姆齐理论，极值图论和一些加法组合问题。曾通过拓展Kim的拉姆齐R(3,t)数的结果，证明了Fox等人提出的关于一个由Burr, Erdos, Lovasz等人引进的拉姆齐理论中的猜想。曾拓展了Conlon, Fox等人关于在线拉姆齐数的几个结果。在进行中的工作有：推广了Bohman, Keevash等人的无H图过程的结果，改进了Bennett, Bohman等人关于超图中独立集的结果，在拉姆齐理论和极值图论中有应用。改进了Sudakov等人关于无三角形图中的最小度的结果，改进了一些范德瓦尔登数的下界。