Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$

Statement

If $R(k)$ is the Ramsey number for $K_k$ (the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$), then \[\frac{R(k)}{k2^{k/2}}\to \infty.\] (erdosproblems.com/1029, statement verbatim)

Facts

- Prize \$100 for a proof; \$1000 offered for a disproof, but Erdős himself calls the disproof offer "to some extent phoney: I am sure that [this] is true (but I have been wrong before)" [Er93,p.337] (quoted verbatim on erdosproblems.com/1029, fetched 2026-07-02). - Status: open; erdosproblems.com states explicitly "This is open, and cannot be resolved with a finite computation." - Falsifiable: no — this asks for the *order of growth* (a limit to infinity) of an asymptotic ratio, not decidable by any finite search; a "disproof" would itself have to be a proof that the ratio stays bounded, which is not a finite-computation task either. - Origin: Erdős, [Er93,p.337]. - Erdős–Szekeres [ErSz35] proved the two-sided classical bracket \[k2^{k/2} \ll R(k) \leq \binom{2k-1}{k-1}.\] The problem is precisely about whether the *lower* side of this bracket is tight in order — Erdős conjectures it is not, i.e. that $R(k)$ grows strictly faster than $k2^{k/2}$, not merely by improving the leading constant. - Best known lower bound on the leading constant (order $k2^{k/2}$ itself, not the polynomial factor asked about here): - Erdős's original probabilistic-method argument: $R(k) \geq (1+o(1))\frac{1}{\sqrt2\,e}k2^{k/2}$ — "one of the first applications of the probabilistic method pioneered by Erdős" (erdosproblems.com/1029). - Spencer [Sp75] (J. Spencer, "Ramsey's theorem — a new lower bound," J. Combin. Theory Ser. A 18 (1975), 108–115, existence/content corroborated via WebSearch and via erdosproblems.com/77's independent citation of the same result), using the Lovász–Erdős Local Lemma, improved the constant by a factor of $2$: \[R(k) \geq (1+o(1))\frac{\sqrt2}{e}k2^{k/2}.\] - This constant-factor-2 improvement by Spencer (1975) is still the best known lower-bound coefficient today — no source found in this search improves it further, and, more importantly for #1029 itself, **no source found improves the *order* $k2^{k/2}$ at all (see Literature state). - Best known upper bound**: the classical Erdős–Szekeres binomial bound $\binom{2k-1}{k-1}\sim 4^k/\sqrt k$ (order-of-magnitude irrelevant to this specific problem, which is purely about the lower-bound side, but stated for completeness). - "See also Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$ for a more general problem concerning $\lim R(k)^{1/k}$, and discussion of upper bounds for $R(k)$" (erdosproblems.com/1029's own cross-reference, verbatim); the reverse link on erdosproblems.com/77 independently confirms #1029 is "a problem concerning a lower bound for $R(k)$." - Related OEIS sequence: A059442 (per erdosproblems.com/1029, same sequence cited on #77). - Formalization: no Lean/Isabelle statement found; erdosproblems.com lists "Formalised statement? No." - 1 comment thread on erdosproblems.com/1029 (user CrashoverrideX marks "interested in collaborating" and "currently working on this problem," no partial results posted).

Literature state

Not resolved anywhere found — genuinely open, and moreover the specific polynomial-factor question of #1029 (order of growth beyond $k2^{k/2}$) appears to be a live, actively-discussed frontier as of 2026, immediately adjacent to work that HAS just broken a 70+-year barrier one notch away:

- Diagonal case ($\ell=k$, exactly what #1029 asks about) — frozen since 1975. No paper found in this search improves the *order* $k2^{k/2}$; only Spencer's 1975 constant-factor-2 gain via the Lovász Local Lemma stands, corroborated independently on erdosproblems.com/77's remarks page (last edited 08 Feb 2026) which likewise records no change to the diagonal lower-bound exponent/order since 1975. - Off-diagonal case ($k=\lambda\ell$, fixed $\lambda>1$) — just broken. Ma, Shen, Xie, "An exponential improvement for Ramsey lower bounds," arXiv:2507.12926 (2025), published Inventiones Mathematicae 2026 (link.springer.com/article/10.1007/s00222-026-01421-9, fetched) prove $r(\ell,C\ell)\geq(p_C^{-1/2}+\varepsilon)^\ell$ for any fixed $C>1$, "the first exponential improvement over the classical lower bound obtained by Erdős in 1947" — but the abstract and the construction are stated only for constant $C>1$. The technique is a spherical/high-dimensional random-geometric-graph coloring (points on the unit sphere in $\mathbb R^d$, edges coloured by an inner-product threshold), exploiting negative correlation among red-clique events and positive correlation among blue-clique events. - The 94-page survey "Some recent results in Ramsey theory" (arXiv:2601.05221, full text read in this search via pdfminer) states this scope restriction explicitly in prose, Section 8: the Ma–Shen–Xie gain is proved "for all pairs $(\ell,k)$ with $k/\ell$ equal to a constant greater than 1," and "if $\ell=k$ then this reduces to Erdős' bound $R(k)\geq2^{-k/2}$" — i.e. at the diagonal endpoint $\lambda=1$ (our #1029), the new machinery is shown by the survey's own authors to degenerate back to the *unimproved* classical bound, not even Spencer's. Whether a further, currently-unpublished refinement pushes all the way to $\lambda=1$ is not claimed anywhere found. - Two independent simplifications of the Ma–Shen–Xie proof exist, both cited in the survey and in the Lin–Niu abstract: Hunter, Milojević, Sudakov, and Sahasrabudhe, both replacing the uniform-sphere construction with i.i.d. Gaussian-coordinate points, giving a cleaner probabilistic (cumulant-generating-function / Gaussian-concentration) proof of the same off-diagonal ($C>1$) result. - Lin, Niu, "Sharper Ramsey lower bounds from refined Gaussian estimates," arXiv:2605.25843 (2026, fetched) push the off-diagonal gain further ("the exponent... can be increased by a strictly positive amount for every fixed $C>1$") via a sharper cumulant-generating-function bound replacing the earlier subgaussian estimate — again explicitly parametrized by fixed $C>1$, not stated to reach $C=1$. - Multicolor case is a genuinely different, informative data point. Conlon, Ferber, "Lower bounds for multicolor Ramsey numbers," arXiv:2009.10458 (2020, first two pages read in full via pdfminer) give "an exponential improvement to the lower bound on diagonal Ramsey numbers for any fixed number of colors greater than two" via a construction over vectors in $\mathbb F_q^t$ with adjacency by scalar product (a finite-field pseudorandom/quadratic-form construction related to one of Alon–Krivelevich) — e.g. $r(t;3)>2^{7t/8+o(t)}$ vs. the old $2^{t/2+o(t)}$-order LLL-only bound. The paper's own introduction states plainly that for the 2-colour case (our diagonal $R(k)$), "only lower-order improvements have been made" in 70 years — i.e. the exact same barrier #1029 is about. A 2026 follow-up, "An update on multicolor Ramsey lower bounds" (arXiv:2601.15183, fetched), further improves the *multicolor* ($r\geq3$) bound by combining Conlon–Ferber/Wigderson/Sawin's density-of-$K_t$-free-graphs reduction with the new Ma–Shen–Xie spherical random-geometric-graph construction — again a genuine technique-transfer between the off-diagonal/multicolor breakthroughs and an *adjacent*, still-two-colour-resistant problem, exactly the shape #1029 has. - Two papers found and read but confirmed irrelevant to a lower-bound-order improvement: Sah, arXiv:2005.09251 (2020) improves the *upper* bound only; a coding-theoretic paper, arXiv:2104.13109, merely re-derives (does not improve) the classical Erdős lower bound from a coding perspective.

Conclusion: #1029 remains genuinely open. But it sits at the exact frontier where three independent 2025-2026 research threads (spherical random geometric graphs for off-diagonal $C>1$; Gaussian-estimate refinements of the same; finite-field pseudorandom constructions for multicolor $r\geq3$) have each broken a barrier immediately adjacent to the diagonal, 2-colour case #1029 asks about, and each paper's own scope statement stops exactly at the boundary #1029 sits on ($C\to1$ or $r\to2$). This is unusually well-timed: the "See also Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$" cross-reference and the survey's own framing suggest the research community is already aware the diagonal case is the natural next target.

Attack surface

- Mode: derivation+formalization (falsifiability is not-finite; a full solution needs a genuine new argument, not a computation — but the "first experiment" below is a concrete, checkable calculation on published formulas, not a search). - Concrete first experiment: take the Ma–Shen–Xie / Hunter–Milojević–Sudakov / Sahasrabudhe / Lin–Niu spherical-or-Gaussian random-geometric-graph construction (arXiv:2507.12926, arXiv:2605.25843) and mechanically evaluate their stated formula $r(\ell,C\ell)\geq(p_C^{-1/2}+\varepsilon(C))^\ell$ (where $C=\log p_C/\log(1-p_C)$) in the limit $C\to1^+$: does $\varepsilon(C)\to0$ (consistent with the survey's claim that $\ell=k$ "reduces to Erdős' bound," i.e. the gain vanishes exactly at the diagonal), or does it approach a positive limit that the original authors simply didn't state because their theorem statement required "fixed $C>1$" for a different, unrelated technical reason (e.g. an error term that is $o(1)$ only away from the diagonal)? This is a direct symbolic/numeric check of an already-published closed-form expression, not new mathematics, and would immediately show whether the barrier is a real obstruction or an artifact of how the theorem was stated. A second, parallel check: does Conlon–Ferber's finite-field/quadratic-form construction (arXiv:2009.10458, "vectors $v\in\mathbb F_q^t$ with $\sum v_i^2 = 0 \bmod q$") have a well-defined $q\to$(2-colour) degenerate case, or does the construction fundamentally require $\geq3$ colours to define the coloring (their paper picks the colour of an edge by *which* of $q$ residue classes the scalar product falls into, which needs $q\geq3$ classes) — if the latter, that is itself a useful negative/structural finding worth recording. - Oracle: for the *general* asymptotic claim, none — any real proof must be checked the normal mathematical way (peer review or eventually a formal proof assistant, as already done for the CGMS23 upper-bound breakthrough referenced on Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$). For the narrower "does the published off-diagonal formula's gain vanish or not as $C\to1$" sub-question above, the oracle is direct symbolic algebra/calculus on the closed-form expressions in arXiv:2507.12926 and arXiv:2605.25843 — fully mechanically checkable without new mathematics. - Feasibility: famous-and-hard as a full solve — this is Erdős's own stated belief about a 90-year-old bracket, actively worked on by top Ramsey-theory groups (Ma–Shen–Xie / Campos–Griffiths–Morris–Sahasrabudhe and collaborators) who have JUST cracked the immediately adjacent off-diagonal and multicolor cases in 2025-2026 using genuinely new probabilistic machinery (random geometric graphs on spheres/Gaussians; finite-field pseudorandom quadratic forms). Realistic near-term angle for us: not "solve #1029" outright, but (a) the concrete formula-limit check above, which is cheap, mechanical, and would produce a genuinely useful (positive or negative) data point that — per this search — nobody has published; (b) tracking this page as the likely next target of the same research groups, given how explicitly their own papers/surveys frame the diagonal case as the boundary they stop short of.

Related

- Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$ — $\lim_{k\to\infty}R(k)^{1/k}$: erdosproblems.com/1029 itself cross-references this as "a more general problem concerning [the same limit], and discussion of upper bounds for $R(k)$"; the reverse link on #77 independently confirms #1029 is "a problem concerning a lower bound for $R(k)$." #1029 is the polynomial-factor refinement of the same $\sqrt2^{\,k}$-order lower bound that #77 brackets exponentially. - concept/probabilistic-method — Erdős's original 1947-style random-colouring argument giving the base $k2^{k/2}$ order (the very bound #1029 asks to beat). - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — Spencer's 1975 technique (J. Combin. Theory Ser. A 18, 108–115) giving the current best constant $\sqrt2/e$, still unbeaten for the diagonal order after 50 years. - concept/random-geometric-graphs — the spherical/Gaussian random-geometric-graph coloring construction (points on $S^{d-1}$ or i.i.d. Gaussian coordinates, edges by inner-product threshold) that broke the off-diagonal ($C>1$) exponential barrier: Ma–Shen–Xie arXiv:2507.12926; simplified by Hunter–Milojević–Sudakov and Sahasrabudhe; sharpened by Lin–Niu arXiv:2605.25843. The most concrete candidate machinery for attacking #1029 if it can be pushed to $C\to1$. - concept/finite-field-pseudorandom-graphs — Conlon–Ferber's quadratic-form-over-$\mathbb F_q^t$ construction (arXiv:2009.10458), related to Alon–Krivelevich, that gave the first exponential lower-bound-order improvement for multicolor ($r\geq3$) diagonal Ramsey numbers but, by the authors' own account, does not extend to $r=2$ — the same "adjacent case broken, diagonal case resistant" pattern as the off-diagonal work above. - concept/multicolor-ramsey-numbers — the $r$-colour generalization; Conlon–Ferber (2020) and the 2026 update (arXiv:2601.15183, combining Conlon–Ferber/Wigderson/Sawin's $K_t$-free-density reduction with the Ma–Shen–Xie construction) show cross-pollination between the multicolor and off-diagonal breakthroughs — a template for how #1029 might eventually be cracked by combining techniques. - concept/book-algorithm — CGMS23's *upper*-bound breakthrough technique (referenced on Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$); included here only as the contrast case — #1029 is squarely a *lower*-bound question, where no comparably novel technique has yet reached the diagonal order.