myWiki/raw/papers/ramsey-sphere-lowerbound.md

title, source, authors, institutions, arxiv, category, date

title	source	authors	institutions	arxiv	category	date
An exponential improvement for Ramsey lower bounds (Raw)	https://arxiv.org/abs/2507.12926	Jie Ma, Wujie Shen, Shengjie Xie	USTC, Tsinghua University, Yau Mathematical Sciences Center	2507.12926v2	math.CO	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