Sharp logarithmic exponents for off-diagonal Ramsey numbers

For every fixed s ≥ 5, the Ramsey number r(s,t) now has its exact power of log t, up to a vanishing error.

2 papers September 24, 2026 Explained by AI

The Ramsey number r(s,t) is the fewest people at a party that guarantees s mutual friends or t mutual strangers. For fixed s, an upper bound of order t^(s−1)/(log t)^(s−2) has stood since 1980. Lower bounds matched the power of t only recently, and still lost a larger power of log t. These two papers prove the upper bound's power of log t is right, up to an error that shrinks as t grows.

First step

1935

Paul Erdős and George Szekeres, the first general upper bound

Significance

Major

It closes the logarithmic gap between lower and upper bounds for a central family of Ramsey numbers.

Trust

Formal proof listed

Field

Combinatorics

2 papers

The explanation

Six people meet at a party. Any two are either friends or strangers. However the friendships fall, some three are all friends, or some three are all strangers. With five people this can fail. Seat them in a ring, make each person friends with the two beside them, and no such trio appears. So the Ramsey number r(3,3) is 6.

In general, r(s,t) is the fewest people that forces s mutual friends or t mutual strangers. In graph terms, a clique is a set of vertices all linked to each other. An independent set has no links at all. Ramsey's theorem from 1930 says these numbers are always finiteSource 1. This entry is about the off-diagonal case: s stays fixed while t grows large.

Upper bounds came first. Erdős and Szekeres gave one in 1935, which grows like t^(s−1). In 1980 Ajtai, Komlós and Szemerédi divided that by (log t)^(s−2)Source 2. That upper bound is where the target power s − 2 comes fromSource 3. For s = 3, Kim showed in 1995 that this upper bound is right up to a constantSource 4.

For larger s, lower bounds lagged far behind. For s = 5, random constructions could not even reach the right power of tSource 5. Finite geometry changed this. In 2026 Bradač built graphs that match the power t^(s−1) for every fixed sSource 6. But his bound divides by (log t)^(2s−4), not (log t)^(s−2). That leftover is the gap these papers closeSource 7.

Put numbers on that gap for s = 5. The upper bound is about t⁴/(log t)³ and Bradač's lower bound is about t⁴/(log t)⁶. Take t equal to one million, so log t is about 13.8. Then (log t)³ is about 2,637 and (log t)⁶ is about 6.95 million. The two bounds differ by a factor of about 2,637.

The first paper proves that for s = 5 the true power of log t is 3Source 8. For every small ε above zero, r(5,t) is at least t⁴/(log t)^(3+ε) once t is large enough. It is at most a constant times t⁴/(log t)³. The second paper proves the same pattern for every fixed s of at least 6, with power s − 2Source 9. The constant factor in front stays openSource 10.

The papers build graphs from geometry over a finite field. Each vertex gets a random point and a random hyperplane through it. A hyperplane is a flat slice one dimension lower than the space. Links depend on which points lie on which hyperplanes. Linear algebra then rules out the forbidden cliqueSource 11. The hard part is the other side: showing no large independent set exists. Picking out one long independent sequence can skew its statistics badlySource 12. The first paper's main new tool describes pairs of point sets and hyperplane sets that meet far less often than expectedSource 13. The second paper gives all its own arguments, including new steps for higher dimensionsSource 14.

How sure is this? A computer proof checker called Lean has checked formal versions of both theorems, with their lower and upper bounds. No specialist review of either paper has been published.

What it doesn't show. This does not cover s = 4, and it does not find the constant factor in front of t^(s−1)/(log t)^(s−2).

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major. Lean checks formal versions of both theorems. The constant factor stays open, s = 4 is not covered, and no specialist review is published.

Words used

Ramsey number r(s,t): The smallest number of vertices that forces either s vertices all linked to each other or t vertices with no links among them.
Clique: A set of vertices in a graph that are all linked to each other.
Independent set: A set of vertices in a graph with no links among them.
Off-diagonal: The case where s stays fixed while t grows, instead of both growing together.
Logarithmic exponent: The power of log t in a formula like t⁴/(log t)³; here it is 3.
o(1): An error term that shrinks toward zero as t grows.

The original papers (2)

The sharp logarithmic exponent of r(5,t) (PDF, opens in a new tab)
September 24, 2026
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers (PDF, opens in a new tab)
September 24, 2026

Lean notes

All quoted lines (14)

Ramsey's finite partition theorem, developed in his work on a problem of formal logic, guarantees that these numbers are finite.
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
Ajtai, Koml\'os, and Szemer\'edi obtained the logarithmic improvement $O_s(t^{s-1}/(\log t)^{s-2})$ .
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
The logarithmic power $s-2$ thus comes from the classical upper-bound side of the problem.
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
For $s=3$ , Kim's lower bound established $r(3,t)=\Theta(t^2/\log t)$ .
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
Thus even the power of $t$ in the upper bound remained out of reach by these methods.
The sharp logarithmic exponent of r(5,t) Back to text
Brada\vc's projective construction then established $r(s,t)\ge c_s\frac{t^{s-1}}{(\log t)^{2s-4}} \qquad(s\ge3,\ t\ge2)$ , determining the polynomial exponent for every fixed $s$ .
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
The remaining difference between the powers $2s-4$ and $s-2$ is the logarithmic gap addressed here.
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
The theorem resolves the sharp logarithmic-exponent question for $r(5,t)$ .
The sharp logarithmic exponent of r(5,t) Back to text
The theorem determines the logarithmic exponent.
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
It leaves open a constant-factor asymptotic for $t^4/(\log t)^3$ .
The sharp logarithmic exponent of r(5,t) Back to text
Linear independence excludes $K_{d+1}$ .
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
Selecting such a sequence can heavily bias its distribution.
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text
The principal additional ingredient is a description theorem for sparse point–hyperplane pairs.
The sharp logarithmic exponent of r(5,t) Back to text
The present paper supplies all the required arguments locally.
Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers Back to text

Other sources

171The hypercube Ramsey conjectureCombinatorics
172Classification of finite Euclidean Ramsey configurationsCombinatorics
160Superexponential van der Waerden numbersCombinatorics
189Cycle–clique Ramsey numbersCombinatorics
169Shareshian–Wachs elementary positivityCombinatorics

Browse Combinatorics Ramsey theory Graph theory Open since before 1940 Lean-checked results