Packing nearly optimal Ramsey R(3,t) graphs

摘要：In 1995 Kim famously proved the Ramsey bound by constructing an n-vertex graph that is triangle-free with proper independence number. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph Kn into a packing of such nearly optimal Ramsey R(3,t) graphs. Our algorithmic proof proceeds by sequentially choosing the graphs via a semi-random (i.e., Ro¨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.

报告人简介：

郭赫博士本科毕业于浙江大学丘成桐数学英才班，现为佐治亚理工数学系博士，导师为Lutz Warnke。

研究方向：Probabilistic Combinatorics, Ramsey Theory, Random Graph Processes, Extremal Combinatorics.