Give an asymptotic formula for $R(3,k)$: pin the constant in $k^2/\log k$ (Erdős #165)
Statement
Let $R(3,k)$ be the least $N$ such that every red/blue colouring of the edges of $K_N$ contains a red triangle $K_3$ or a blue clique $K_k$. Give an asymptotic formula for $R(3,k)$ as $k\to\infty$. It is known that $R(3,k)=\Theta\!\left(k^2/\log k\right)$; the problem is to determine the precise asymptotics — in particular the value of the constant $c$ in $R(3,k)\sim c\,k^2/\log k$, and whether this limit exists.
Acceptance. FULLY RESOLVES: a proof establishing the exact asymptotic constant — that $\lim_{k\to\infty} R(3,k)\,\log k / k^2$ exists and equals a specific value (the conjecture is $1/2$), with matching upper and lower bounds. Machine-checkable (Lean/Coq) preferred, otherwise a complete written proof. ADVANCES, each checkable: (a) raise the lower-bound constant strictly above the best value stated in the background (currently $c\ge 1/2$), or lower the upper-bound constant strictly below the best stated (currently $1$), with a complete proof; (b) extend the table of exact values $R(3,k)$ (OEIS A000791) via a verified computation together with a certificate of correctness. State the new constant or value in words and prove it strictly beats the background. Deliver the proof file, or the code plus the new value and its certificate.
Background
Asked repeatedly by Erdős [Er61], [Er71], [Er78, p.34], [Er90b], [Er93, p.339], [Er97c]; the site records a prize of $250. It is known that for large $k$, $(c+o(1))\frac{k^2}{\log k}\le R(3,k)\le (1+o(1))\frac{k^2}{\log k}$. The upper bound is due to Shearer [Sh83], improving Ajtai–Komlós–Szemerédi [AKS80]; the matching order lower bound $\gg k^2/\log k$ is due to Kim [Ki95]. The lower-bound constant has been pushed up repeatedly: Kim's original proof gave $c\ge 1/162$; $c\ge 1/4$ was proved independently by Bohman–Keevash [BoKe21] and by Fiz Pontiveros–Griffiths–Morris [PGM20] (who conjectured $1/4$ is the truth); then $c\ge 1/3$ by Campos–Jenssen–Michelen–Sahasrabudhe [CJMS25], and $c\ge 1/2$ by Hefty–Horn–King–Pfender [HHKP25], the last two teams conjecturing $c=1/2$ is correct, i.e. $R(3,k)\sim \tfrac12 k^2/\log k$. So the remaining gap is entirely in the constant, currently trapped between $1/2$ (lower) and $1$ (upper). Relevant sequence: OEIS A000791 (exact values of $R(3,k)$). Closely related to Erdős #544 (consecutive differences $R(3,k+1)-R(3,k)$, erdosproblems.com/544) and to the general off-diagonal case #986; distinct from the venue's small-value problem 'Determine or bound small Ramsey numbers beyond current records', which targets exact numbers rather than this asymptotic constant. Listed as open on erdosproblems.com/165 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory. Attacker's tool: refined analysis of the triangle-free process / random-greedy independent sets to raise the lower constant, entropy and hypergraph-container methods to lower the upper constant toward a common $1/2$, and SAT/enumeration to extend the exact values (OEIS A000791) that anchor the conjecture.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #165 (T. F. Bloom) | website |
| REF-02 | OEIS A000791 — Ramsey number R(3,n) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.