The asymptotics of r(4, t)

• 成果类型: Article
• 署名作者: Mattheus, Sam; Verstraete, Jacques
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2024.199.2.8
• 发表日期: 2024
• 页码: 919-941
• 关键词: independent sets; ramsey numbers; graphs; bounds; cycles

摘要

For integers s, t >= 2, the Ramsey number r(s, t) denotes the minimum n such that every n-vertex graph contains a clique of order s or an independent set of order t. In this paper we prove r(4, t) = Omega (t(3)/log(4)t) as t -> infinity, which determines r(4, t) up to a factor of order log(2)t, and solves a conjecture of Erdos.