Abstract

We prove a new lower bound on the Ramsey number r(\ell, C\ell) for any constant C> 1 and sufficiently large \ell, showing that there exists \varepsilon(C) > 0 such that r(\ell, C\ell) ≥ \left(p_C^{-1/2} + \varepsilon(C)\right)^\ell, where p_C denotes the unique solution in (0, 1/2) satisfying C = \log p_C / \log (1 - p_C). This provides the first exponential improvement over the classical lower bound by Erdos since 1947. Joint work with Wujie Shen and Shengjie Xie.

个人简介

马杰，中国科学技术大学/清华大学教授，从事组合图论领域的研究工作及其在理论计算机和信息科学中的应用，在极值组合、结构图论和概率组合等领域分支取得了系列理论创新成果。曾获海外高层次人才引进计划青年项目、基金委优秀青年科学基金项目、基金委国家杰出青年科学基金项目，担任科技部国家重点研发计划项目负责人、基金委数学天元基金学术领导小组成员、JCTB和SIDMA等杂志编委。