An exponential improvement for diagonal Ramsey

2023/03/16 by Marcelo Campos, Campos, Marcelo, Simon Griffiths +5 · 2 voices · 9 citations
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.2303.09521

arxiv published 2023/03/16 · arxiv updated 2025/08/04

Abstract

The Ramsey number R(k) is the minimum n ∈ ℕ such that every red-blue colouring of the edges of the complete graph K_n on n vertices contains a monochromatic copy of K_k. We prove that R(k) \leqslant (4 - ε)^k for some constant ε > 0. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935.

Cited by

• A linear upper bound for zero-sum Ramsey numbers of bounded degree graphs
• Gaussian random graphs and Ramsey numbers
• A note on the maximum ratio between chromatic number and clique number
• Online Ramsey turnaround numbers
• Lower and Upper Bounds for Small Canonical and Ordered Ramsey Numbers
• Graphs with asymmetric Ramsey properties
• Improving R(3,k) in just two bites
• Ramsey numbers of long even cycles versus books
• Can Language Models Discover Scaling Laws?

Discussions

• An exponential improvement for diagonal Ramsey [hn, 3 points, 2 comments]
• An exponential improvement for diagonal Ramsey (numbers) [hn, 1 points, 1 comments]

Related

• Upper bounds for multicolour Ramsey numbers
• An exponential upper bound for induced Ramsey numbers
• The pigenhole principle and multicolor Ramsey numbers
• A lower bound for set-colouring Ramsey numbers
• Recent developments in graph Ramsey theory