A new lower bound for the Ramsey numbers R(3,k)

2025/05/19 by Marcelo Campos, Campos, Marcelo, Matthew Jenssen +5 · 6 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2505.13371

openalex publication_date 2025/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove a new lower bound for the off-diagonal Ramsey numbers, R(3,k) ≥ ( (1)/(3)+ o(1) ) (k²)/(log k ) , thereby narrowing the gap between the upper and lower bounds to a factor of 3+o(1). This improves the best known lower bound of (1/4+o(1))k²/log k due, independently, to Bohman and Keevash, and Fiz Pontiveros, Griffiths and Morris, resulting from their celebrated analysis of the triangle-free process. As a consequence, we disprove a conjecture of Fiz Pontiveros, Griffiths and Morris that the constant 1/4 is sharp.

Cited by

• A linear upper bound for zero-sum Ramsey numbers of bounded degree graphs
• Gaussian random graphs and Ramsey numbers
• Probabilistic combinatorics at exponentially small scales
• A polynomial improvement for the odd cycle-complete Ramsey numbers
• Improving R(3,k) in just two bites
• The Sunflower-Free Process

Related

• Improving R(3,k) in just two bites
• The triangle-free process and the Ramsey number R(3,k)
• Off-diagonal Ramsey numbers
• Optimizing the CGMS upper bound on Ramsey numbers
• A note on lower bounds for hypergraph Ramsey numbers