Erdős #165 — asymptotic formula for the Ramsey number R(3,k)

Statement

Give an asymptotic formula for $R(3,k)$, the off-diagonal Ramsey number: the least $n$ such that every red/blue colouring of the edges of $K_n$ contains a red triangle or a blue independent set of size $k$. (erdosproblems.com/165, citing [Er61],[Er71],[Er78,p.34],[Er90b],[Er93,p.339],[Er97c])

Facts

- Prize $250; status open on erdosproblems.com ("cannot be resolved with a finite computation" — it is an asymptotic/growth-rate claim, not a finite search target). - Falsifiable: no. Only a genuine proof pinning the constant can resolve it; no finite computation can decide an asymptotic-formula question. - Origin: Erdős, six references spanning 1961–1997 ([Er61],[Er71],[Er78,p.34],[Er90b],[Er93,p.339],[Er97c]); this is one of Erdős's most repeated/favourite problems. - Known results / best bounds (all verified on erdosproblems.com/165, cross-checked against the primary papers): $$\left(\tfrac12+o(1)\right)\frac{k^2}{\log k}\;\leq\;R(3,k)\;\leq\;\left(1+o(1)\right)\frac{k^2}{\log k}.$$ - Upper bound $\leq(1+o(1))k^2/\log k$: Shearer [Sh83] (1983), improving the semi-random-method paper of Ajtai–Komlós–Szemerédi [AKS80] (1980). Unimproved since 1983. - Lower bound history: Kim [Ki95] (1995) first got the correct order $\Omega(k^2/\log k)$ via the "nibble" (semi-random deletion) method, with constant $c\approx1/162$. Bohman–Keevash [BoKe21] and Fiz Pontiveros–Griffiths–Morris [PGM20] (2013/2020) independently pushed $c\geq1/4$ via a full dynamic-concentration analysis of the *triangle-free process*; PGM20 conjectured $1/4$ was optimal. Campos–Jenssen–Michelen–Sahasrabudhe [CJMS25] = arXiv:2505.13371 (May 2025) disproved that conjecture, giving $c\geq1/3$ via a denser-than-triangle-free-process pseudorandom construction. Hefty–Horn–King–Pfender [HHKP25] = arXiv:2510.19718 (Oct 2025) pushed further to $c\geq1/2$ with a simpler, nibble-free "two bites" random construction. Both CJMS25 and HHKP25 conjecture $c=1/2$ is the true asymptotic constant, i.e. that $R(3,k)\sim\frac12\frac{k^2}{\log k}$. - The gap between upper (1) and lower (1/2) bound constants is now exactly a factor of 2 — narrowed from a factor of 162 (Kim, 1995) over 30 years. - HHKP25 explicitly identify the missing piece for a full resolution: the Davies–Jenssen–Perkins–Roberts conjecture (arXiv:1606.01043, Proc. Amer. Math. Soc. 2018) about *maximum* vs *average* independent-set size in triangle-free graphs (via the hard-core-model/occupancy-fraction method) — if the max-independent-set analogue of their average-case theorem holds with the matching constant, it would supply the missing upper bound $c\leq1/2$, fully proving Erdős's asymptotic conjecturally at $R(3,k)\sim\frac12 k^2/\log k$. - Both HHKP25's proof and a related paper — Bradač, "Off-diagonal Ramsey numbers" arXiv:2605.28793 (which proves the general-$s$ lower bound $r(s,k)\gg k^{s-1}/(\log k)^{2s-4}$, weaker than $1/\log k$ for $s=3$, so does not affect #165's best bound) — have been autoformalized in Lean by the Trellis system (an LLM-agent-driven autoformalizer, math.cmu.edu/~wes/trellis.php; ChatGPT Pro/Codex agents under a deterministic supervisor, human input limited to approving Lean statement shapes; the Bradač formalization cost ≈$18 in compute). - Related problems: erdos/544 — is $R(3,k+1)-R(3,k)\to\infty$? (open, weaker/orthogonal question about increments, not the asymptotic constant). erdos/986 — the general-$s$ version $R(s,k)\gg k^{s-1}/(\log k)^{c(s)}$, PROVED for all fixed $s\geq3$ (Spencer $s=3$ 1977, Mattheus–Verstraete $s=4$, Bradač $s\geq5$ arXiv:2605.28793) but only gives *order of magnitude with unspecified constant*, not the sharp asymptotic #165 demands. erdos/1013 — $h_3(k)$, minimal $n$ for a triangle-free graph with chromatic number $k$; a "dual" extremal function using the same triangle-free-graph machinery. erdos/166 — the $R(4,k)$ analogue, already PROVED (order of magnitude only) by Mattheus–Verstraete [MaVe23]=arXiv:2306.04007 using an algebraic pseudorandom construction. erdos/1014 — closely adjacent Ramsey-increment question, already solved and Lean-verified by "an internal model at OpenAI" per erdosproblems.com. erdos/1030 — $R(k+1,k)/R(k,k)>1+c$, open, same Erdős–Sós circle of increment questions as #544.

Literature state

Not resolved. Still genuinely open — but the frontier moved substantially in 2025 and the gap is now the narrowest it has ever been (factor of 2, constant $1/2$ vs $1$). Two independent papers within 6 months of each other advanced the lower-bound constant: Campos, Jenssen, Michelen, Sahasrabudhe (arXiv:2505.13371, May 2025) went from $c=1/4$ to $c\geq1/3$ using a pseudorandom construction denser than the classical triangle-free process (sample a sparser random graph on $n/(\log n)^2$ vertices, delete triangles, blow it up, then run a variant of the triangle-free process on top — this breaks the previous belief, held by Bohman–Keevash and Fiz Pontiveros–Griffiths–Morris, that the triangle-free process itself was extremal). Hefty, Horn, King, Pfender (arXiv:2510.19718, Oct 2025, v3 Feb 2026) then improved this to $c\geq1/2$ with a technically simpler "flexible random construction" that avoids the nibble method entirely, explicitly inspired by the "book algorithm" ideas behind Campos–Griffiths–Morris–Sahasrabudhe's 2023 exponential improvement to the *diagonal* Ramsey number upper bound (arXiv:2303.09521, the first improvement since Erdős–Szekeres 1935). Both 2025 papers conjecture $c=1/2$ is exactly right, which combined with Shearer's 1983 upper bound would give $R(3,k)\sim\frac12\frac{k^2}{\log k}$ — but neither proves the matching upper bound, and Shearer's constant of $1$ has not moved since 1983.

The single most concrete, named path to closing the gap is stated explicitly in HHKP25's own paper: a conjecture of Davies, Jenssen, Perkins, Roberts (arXiv:1606.01043, PAMS 2018) about the occupancy fraction / hard-core-model behaviour of triangle-free graphs of bounded degree $d$ (they proved a tight *average*-independent-set-size bound $(1+o_d(1))\frac{\log d}{d}n$ giving an alternative derivation of Shearer's upper bound; the analogous statement about the *maximum* independent set, if it holds with the matching constant, would prove $R(3,k)\leq(\tfrac12+o(1))k^2/\log k$ and settle #165 completely). No source found claims this DJPR-max-version conjecture has been proven.

HHKP25's construction is explicitly noted (in their own paper, Section on generalizations) to already be reused for other extremal problems: a polynomial improvement to cycle-complete Ramsey numbers $r(C_\ell,K_k)$ (Campos–Jenssen–Michelen–Pfender–Sahasrabudhe, arXiv:2511.10641) and Kühn–Sauermann–Steiner–Wigderson's disproof of the odd Hadwiger conjecture (arXiv:2512.20392) — i.e. it is a genuinely fertile new technique beyond just R(3,k). A January 2026 survey, "Some recent results in Ramsey theory" (arXiv:2601.05221), situates R(3,k)/R(4,k) lower-bound progress alongside the exponential diagonal/near-diagonal/multicolor Ramsey breakthroughs and induced-Ramsey upper bounds as the current frontier of the field — confirming no further improvement to #165 beyond HHKP25 was reported as of Jan 2026.

AI-system involvement, directly on record: (1) erdosproblems.com/1014 — a Ramsey problem in the immediate neighborhood of #165 (about $\lim_{l\to\infty}R(k,l+1)/R(k,l)=1$ for fixed $k$) — states it "has been solved by an internal model at OpenAI," with the proof Lean-verified (status "PROVED (LEAN)"). (2) erdosproblems.com/986 (the general-$s$ version of #165) notes an exponent correction in Bradač's proof was "observed by an internal model at OpenAI." (3) Both HHKP25's R(3,k) paper and Bradač's off-diagonal paper have been autoformalized end-to-end in Lean by the Trellis system (math.cmu.edu/~wes/trellis.php), an LLM-agent (ChatGPT Pro/Codex) autoformalizer with a deterministic supervisor; formalization of the Bradač paper took ~40 hours wall-clock and ~$18 of compute with essentially no human mathematical input. No source found claims any AI system has attempted #165 itself (the sharp-asymptotic question) — all AI touches found are on adjacent/easier problems (order-of-magnitude-only #986, increment-ratio #1014) or on formalizing existing human proofs, not on producing new mathematics toward closing the $1/2$-vs-$1$ gap.

Attack surface

- Mode: derivation+formalization. This is not a finite-search problem (falsifiability: not-finite) — it requires either (a) a genuinely new upper-bound proof beating Shearer's 1983 constant of $1$, or (b) proving the Davies–Jenssen–Perkins–Roberts max-independent-set conjecture (which HHKP25 identify as sufficient to reach $c=1/2$ and match their lower bound), or (c) an incremental lower-bound push beyond HHKP25's $c\geq1/2$ (unlikely to be fruitful since $1/2$ is conjectured optimal by both current best papers). - Concrete first experiment: (1) Precisely state the Davies–Jenssen–Perkins–Roberts "average vs. maximum independent set" conjecture from arXiv:1606.01043 in max-independent-set form, and check the literature (Semantic Scholar citation graph of 1606.01043, ~2018–2026) for any partial progress on the *max*-version specifically — this is a well-defined, bounded literature-search task, distinct from re-deriving it ourselves. (2) Read HHKP25's Section 2 construction in full (the PDF was fetched to /tmp/.../2510.19718.pdf in this session) to identify whether their "two bites" pseudorandom construction, run with a max-independent-set-aware stopping rule instead of their current one, could plausibly be pushed toward $c>1/2$ or instead toward matching DJPR's constant from the upper-bound side — i.e. check if the same construction family gives both directions. - Oracle: none computational — any candidate proof must be checked the standard way (referee-grade extremal/probabilistic-combinatorics proof verification), consistent with the site's own "not resolvable by finite computation" flag. A Lean formalization (as done for HHKP25 via Trellis) would be a strong mechanical secondary check once a proof exists, but cannot itself discover the proof. - Feasibility: famous-and-hard, but with a rare, extremely well-defined 30-year-narrowed target: the gap is now literally "prove upper bound $1/2$" vs "known upper bound $1$" with a named, citable candidate conjecture (DJPR, arXiv:1606.01043) that would close it if proven for the max-independent-set case. This is not a problem where we can add value by literature search alone (it is genuinely open, confirmed by a Jan 2026 survey), but the DJPR-conjecture route is a concrete, narrow, well-posed sub-target — closer to "derive one missing lemma" than "invent a new field," which is unusual for a 65-year-old Erdős problem. Realistic near-term contribution: a focused literature/derivation pass specifically on the max-vs-average independent-set gap in triangle-free bounded-degree graphs (hard-core model / occupancy-fraction method), not a general attack on R(3,k).

Related

- erdos/544 — is $R(3,k+1)-R(3,k)\to\infty$ (and is it $o(k)$)? Open; a weaker increment question in the same $R(3,k)$ family, whose remarks explicitly reference #165's bounds. - erdos/986 — general-$s$ version $R(s,k)\gg k^{s-1}/(\log k)^{c(s)}$; PROVED for all $s\geq3$ (order of magnitude only, not sharp constant); #165 is exactly the $s=3$ sharp-constant refinement of this. - erdos/166 — the $R(4,k)$ sibling problem, already PROVED (order of magnitude) by Mattheus–Verstraete arXiv:2306.04007 via an algebraic pseudorandom construction — a genuinely different (non-probabilistic) technique family worth checking against #165's constant-sharpening goal. - erdos/1013 — $h_3(k)$, chromatic-number dual of the triangle-free extremal-graph machinery underlying #165's lower-bound constructions. - erdos/1014 — adjacent Ramsey-ratio problem, already solved and Lean-verified, attributed to "an internal model at OpenAI" on erdosproblems.com — direct evidence of AI-system success in this exact problem neighborhood (though not on #165 itself). - erdos/1030 — $R(k+1,k)/R(k,k)>1+c$; same Erdős–Sós circle of Ramsey-increment questions. - concept/triangle-free-process — the random greedy graph process (Bohman–Keevash arXiv, Fiz Pontiveros–Griffiths–Morris Mem. AMS 2020) whose dynamic-concentration analysis gave $c\geq1/4$; superseded as the presumed-extremal construction by CJMS25's denser pseudorandom variant. - concept/nibble-method — Kim's semi-random deletion method (1995), the original technique establishing $R(3,k)=\Theta(k^2/\log k)$; also the classical Ajtai–Komlós–Szemerédi semi-random method underlying the 1980/1983 upper bound. - concept/occupancy-fraction-method — the hard-core-model / occupancy-fraction technique of Davies–Jenssen–Perkins–Roberts (arXiv:1606.01043) giving an alternative proof of Shearer's upper bound via average independent-set size; the unresolved max-independent-set analogue is the identified missing piece for fully resolving #165. - concept/book-algorithm — the technique behind Campos–Griffiths–Morris–Sahasrabudhe's 2023 exponential improvement to diagonal Ramsey numbers (arXiv:2303.09521), explicitly cited as inspiration by HHKP25 for their off-diagonal $R(3,k)$ construction. - concept/pseudorandom-triangle-free-construction — the CJMS25/HHKP25 family of constructions (sample-clean-blowup, "two bites") that beat the triangle-free process's density while preserving pseudorandomness; also reused in arXiv:2511.10641 (cycle-complete Ramsey numbers) and arXiv:2512.20392 (disproof of the odd Hadwiger conjecture). - concept/lean-autoformalization-agent — the Trellis system (math.cmu.edu/~wes/trellis.php), an LLM-agent (ChatGPT Pro/Codex) autoformalizer with deterministic supervision, which has formalized both HHKP25 and Bradač's off-diagonal Ramsey papers in Lean at ~$18–?? compute cost per paper.