An exponential improvement for Ramsey lower bounds

2025/07/17 by Jie Ma, Wujie Shen, Ma, Jie +3 · 3 voices · 6 citations
#math.CO

paper · pdf · doi:10.48550/arxiv.2507.12926

Abstract

We prove a new lower bound on the Ramsey number r(ℓ, Cℓ) for any constant C > 1 and sufficiently large ℓ, showing that there exists ε=ε(C)> 0 such that r(ℓ, Cℓ) ≥ (p_C^-1/2 + ε)^ℓ, where p_C ∈ (0, 1/2) is the unique solution to C = (log p_C)/(log(1 - p_C)). This provides the first exponential improvement over the classical lower bound obtained by Erdős in 1947.

Citations

• The early evolution of the H-free process
• On a Problem of Formal Logic

Cited by

• Distinguishability threshold for random geometric graphs
• Off-diagonal Ramsey numbers
• A linear upper bound for zero-sum Ramsey numbers of bounded degree graphs
• Gaussian random graphs and Ramsey numbers
• Is Dimensionality a Barrier for Retrieval Models?
• Rare event probabilities in Random Geometric Graphs

Discussions

• An exponential improvement for Ramsey lower bounds [hn, 37 points, 1 comments]
• An exponential improvement for Ramsey lower bounds https://arxiv.org/abs/2507.12926 (https://news.ycombinator.com/item?id=44613947) [bsky, 0 points, 0 comments]
• An exponential improvement for Ramsey lower bounds https://arxiv.org/abs/2507.12926 [bsky, 0 points, 0 comments]

Related

• A polynomial improvement for the odd cycle-complete Ramsey numbers
• A note on lower bounds for hypergraph Ramsey numbers
• Exponential lower bound for Berge-Ramsey problems
• Optimizing the CGMS upper bound on Ramsey numbers
• An exponential improvement for diagonal Ramsey