2026/05/27 by Domagoj Bradač · 3 voices
#math.CO
For positive integers s and k, the Ramsey number r(s,k) is the minimum integer n such that any graph on n vertices contains a clique of size s or an independent set of size k. We prove that for any fixed s ≥ 3 and k tending to infinity, the off-diagonal Ramsey numbers satisfy r(s, k) ≥ Ω(\fracks-1(log k)2s-4 ), which matches, up to polylogarithmic factors, the upper bound established over 90 years ago by Erdős and Szekeres. For s ≥ 5, this improves the best known lower bound of the form r(s, k) ≥ k(s+1)/(2) + o(1) which was first established by Spencer in 1977 and has since only seen polylogarithmic improvements.