66 lines
3.0 KiB
Markdown
66 lines
3.0 KiB
Markdown
---
|
||
title: "An exponential improvement for Ramsey lower bounds (Raw)"
|
||
source: https://arxiv.org/abs/2507.12926
|
||
authors: Jie Ma, Wujie Shen, Shengjie Xie
|
||
institutions: USTC, Tsinghua University, Yau Mathematical Sciences Center
|
||
arxiv: 2507.12926v2
|
||
category: math.CO
|
||
date: April 28, 2026
|
||
---
|
||
|
||
# An Exponential Improvement for Ramsey Lower Bounds
|
||
|
||
## 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ℓ) ≥ (M_C + ε)^ℓ, where M_C = p_C^{-1/2}, and 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.
|
||
|
||
## 1. Introduction
|
||
|
||
The Ramsey number r(ℓ, k) denotes the smallest positive integer n such that every red-blue edge coloring of the complete graph K_n on n vertices contains either a red clique K_ℓ or a blue clique K_k.
|
||
|
||
**History of upper bounds**:
|
||
- 1935: Erdős-Szekeres — r(ℓ, k) ≤ C(k+ℓ-2, ℓ-1)
|
||
- 1988: Thomason — first polynomial improvement
|
||
- 2009: Conlon — superpolynomial improvement via quasi-randomness
|
||
- 2013: Sah — refined optimization
|
||
- 2023: Campos, Griffiths, Morris, Sahasrabudhe — first exponential improvement: r(ℓ, k) ≤ e^{-ℓ/400+o(k)}·C(k+ℓ, ℓ)
|
||
- 2025: Gupta, Ndiaye, Norin, Wei — improved to r(ℓ, ℓ) ≤ 3.8^{ℓ+o(ℓ)}
|
||
|
||
**History of lower bounds**:
|
||
- 1947: Erdős — probabilistic method: r(ℓ, Cℓ) = Ω(ℓ·M_C^ℓ)
|
||
- 1975: Spencer — Lovász Local Lemma constant-factor refinement
|
||
- 2026: **This paper** — first exponential improvement
|
||
|
||
## Theorem 1.1 (Main Result)
|
||
|
||
For any constant C > 1, there exist ε = ε(C) > 0 and ℓ₀ = ℓ₀(C) > 0 such that for all ℓ ≥ ℓ₀(C),
|
||
|
||
r(ℓ, Cℓ) ≥ (M_C + ε)^ℓ
|
||
|
||
where M_C = p_C^{-1/2}, and p_C ∈ (0, 1/2) satisfies C = log p_C / log(1-p_C).
|
||
|
||
## Corollary 1.2 (General Regime)
|
||
|
||
For any δ ∈ (0, 1/2), r(ℓ, k) ≥ (1+2c_δ)^ℓ · (M_{k/ℓ})^ℓ ≥ (1+c_δ)^ℓ · Er(ℓ, k) whenever δ ≤ ℓ/k ≤ 1-δ.
|
||
|
||
## Corollary (Almost Diagonal)
|
||
|
||
For √ℓ ≪ f(ℓ) ≪ ℓ: r(ℓ, ℓ+f(ℓ)) ≥ e^{Ω(f(ℓ)²/ℓ)} · Er(ℓ, ℓ+f(ℓ))
|
||
|
||
## 2. The Random Sphere Graph G_{k,p}(n)
|
||
|
||
A novel random graph model based on geometric measure:
|
||
- Sample n points uniformly at random from the k-dimensional unit sphere S^k ⊂ R^{k+1}
|
||
- Connect each pair independently with probability p
|
||
- Unlike G(n,p), the edge probability is governed by geometric proximity
|
||
|
||
## 3-9. Proof Structure
|
||
|
||
1. **Section 3**: Reduce Theorem 1.1 to Theorem 3.1 (core technical result)
|
||
2. **Section 4**: Auxiliary lemmas (geometric measure estimates)
|
||
3. **Section 5**: Introduce perfect sequences for unit vectors
|
||
4. **Section 6**: Preliminary estimates on perfect sequences
|
||
5. **Section 7**: Show perfect sequences capture essential behavior
|
||
6. **Section 8**: Core technical arguments — estimates on key quantities
|
||
7. **Section 9**: Assemble all estimates to complete proof of Theorem 3.1
|