Off-diagonal Ramsey r(4,t): closing the log² t gap between t³/log⁴ t and t³/log² t
A log² t factor remains after a major 2023 construction, and the claimed s ≥ 5 results (if correct) suggest the AKS bound is the truth, so 55: research-grade, well below diagonal Ramsey (78). Application value 6 is indirect (pseudorandom constructions). Leverage 25: limited to Ramsey theory and algebraic pseudorandom graphs.
The problem
How large must a network be to contain either four mutual friends or t mutual strangers? Pin down the missing logarithmic factors.
- 1Need 4 mutual friends or t strangers
- 2Size grows like t cubed, up to logs
- 3Lower bound by a structured-plus-random graph
- 4Open: the exact power of log t
Definition. Let be the least such that every graph on vertices contains a (four mutually adjacent vertices) or an independent set of size (no two adjacent). Equivalently, 2-colour the edges red and blue; this is the Ramsey number for a red or a blue .
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- Off-diagonal Ramsey r(4,t): closing the log² t gap between t³/log⁴ t and t³/log² tThe problem
State of the art
Partially resolved. Before Mattheus–Verstraete the best lower bound was t^(5/2) up to logarithms (Bohman–Keevash, via the K_4-free process). Their construction (arXiv:2306.04007, Annals 199 (2024)) takes a random induced subgraph of a pseudorandom graph built from the Hermitian unital over a finite field, giving t³/log⁴ t. For r(3,t) the order t²/log t has been known since Kim (1995) and Ajtai–Komlós–Szemerédi, with the constant now within a small factor after the triangle-free process (Bohman–Keevash; Fiz Pontiveros–Griffiths–Morris) and later work. OpenAI's 6 October 2026 release (github.com/openai/math, family 170; unrefereed, with a Lean formalization listed) claims r(s,t) = t^(s−1)/(log t)^(s−2+o(1)) for every fixed s ≥ 5, matching the AKS upper bound; the claim explicitly excludes s = 4, which stays open between log² and log⁴.
Realistic applications
None directly. The constructions (algebraic pseudorandom graphs, random greedy processes such as the H-free process) are reused in extremal and probabilistic combinatorics.
What counts as solved
A proof that r(4,t) = Θ(t³/log^a t) for a definite a, or any improvement in the power of log, accepted after refereeing.
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
The target is r(4,t) = Θ(t³/log^a t) for a definite a, or a smaller power of log in the gap. Formal Conjectures (Formal Conjectures pinned at commit e754a78 (17 October 2026)) states only the solved lower bound (ErdosProblems/166.lean, Mattheus–Verstraete, with a linked Lean proof of a weaker form), not the open exponent question. Referees check the proof.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Constructions in finite geometry and probabilistic analysis; computation helps search small cases.
Bottlenecks
ranked by votes- #1TheoryPseudorandom K_4-free graph construction
The unital-based pseudorandom graph loses log factors when its independence number is controlled after sparsification; matching AKS needs a K_4-free graph that is pseudorandom at a finer scale.
Community grades
Sign in to add your own grade.