Erdős #159 — polynomial improvement to R(C4,Kn) upper bound

Statement

There exists a constant $c>0$ such that $$R(C_4,K_n) \ll n^{2-c}.$$

(Here $R(C_4,K_n)$ is the smallest $N$ such that every 2-colouring of the edges of $K_N$ contains a red $C_4$ or a blue $K_n$.)

Facts

- Prize $100; status OPEN, "cannot be resolved with a finite computation" (erdosproblems.com/159, reflects site-owner belief, page last edited 2026-03-07). - Falsifiable: no — this needs a genuine proof (an upper-bound statement quantified over all $n$); no finite computation settles it. - Origin: Erdős [Er78, p.34], restated in [Er81] and [Er84d]. Also listed as #17 in Ramsey Theory in the "graphs problem collection" (mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/RamseyC4.html). - Known results / best bounds (erdosproblems.com/159): $$\frac{n^{3/2}}{(\log n)^{3/2}} \ll R(C_4,K_n) \ll \frac{n^2}{(\log n)^2}.$$ Upper bound due to Szemerédi (unpublished, mentioned in Erdős–Faudree–Rousseau–Schelp [EFRS78], *On cycle-complete graph Ramsey numbers*, J. Graph Theory 1978). Lower bound due to Spencer [Sp77], *Asymptotic lower bounds for Ramsey functions*, Discrete Math. 20 (1977), 69–76, via the Lovász Local Lemma. Independently confirmed current (as of Nov 2025) by Campos–Jenssen–Michelen–Pfender–Sahasrabudhe [arXiv:2511.10641], §1.1: "For the upper bound, Erdős proved in the 1950s that $r(C_\ell,K_k)\le c_\ell n^{1+2/(\ell-2)}$ [for even $\ell$], which has only been improved by polylogarithmic factors by Caro, Li, Rousseau, and Zhang [caro2000asymptotic]. For even $\ell$ it is much less clear if Erdős's upper bound is sharp. Indeed, it is a beautiful conjecture of Erdős that $r(C_4,K_k)\le k^{2-\varepsilon+o(1)}$ for some $\varepsilon>0$" — this is a verbatim restatement of problem 159, read directly from the arXiv HTML source. - Related problems: Erdős #165 — asymptotic formula for the Ramsey number R(3,k), erdos/166.

Literature state

Genuinely searched arXiv, OpenAlex/Semantic Scholar (rate-limited), Google-style web search, and the erdosproblems.com bibliography/forum/AI-contributions wiki. Findings:

- Not resolved anywhere. The most recent paper that explicitly discusses this exact question, Campos–Jenssen–Michelen–Pfender–Sahasrabudhe, *A polynomial improvement for the odd cycle–complete Ramsey numbers* (arXiv:2511.10641, Nov 2025), states plainly (read in full, §1.1): "In the case of even $\ell$, there are no known examples that beat the deletion threshold by a polynomial factor" and reiterates the Erdős conjecture $r(C_4,K_k)\le k^{2-\varepsilon+o(1)}$ as open. This is the freshest touchpoint (≤8 months before today, 2026-07-02) and it explicitly leaves $\ell=4$ (and even $\ell$ generally) untouched by its new "randomly superimposed blow-up" method. - 0 forum comments on erdosproblems.com/159; no entry for #159 in the teorth/erdosproblems "AI contributions to Erdős problems" wiki (checked via raw wiki markdown, no match) — no AI system has recorded a claimed contribution to this problem. - The analogous odd-cycle problem has been broken, but not the even one. For odd $\ell$, the *lower*-bound side saw two waves of polynomial improvements: (i) Mubayi–Verstraëte (2024) broke the "deletion-threshold barrier" for $\ell\in\{5,7\}$ via incidence graphs of generalized hexagons, giving $r(C_5,K_k)\ge k^{11/8}$, $r(C_7,K_k)\ge k^{11/9}$ (cited in arXiv:2511.10641 as mubayi2024, "A note on Pseudorandom Ramsey graphs", EMS Press, ems.press/content/serial-article-files/42561); (ii) Conlon–Mattheus–Mubayi–Verstraëte, *Ramsey numbers and the Zarankiewicz problem*, Bull. LMS (2024), pushed this to $r(C_5,K_k)\ge k^{10/7-o(1)}$, $r(C_7,K_k)\ge k^{5/4-o(1)}$ by leveraging the finite-geometry construction from the $R(4,t)$ breakthrough. Then arXiv:2511.10641 itself gives the first polynomial improvement for all odd $\ell>7$, via a new "randomly superimposing blow-ups of random graphs" construction (credited to Hefty–Horn–King–Pfender 2025, inspired by Campos–Jenssen–Michelen–Sahasrabudhe 2025). None of this machinery is claimed to extend to even $\ell$; the authors state it explicitly. - Why the even case ($\ell=4$) is structurally different and harder: all the above are *lower*-bound (construction) improvements on the Ramsey-theoretic *twin* question. Problem 159 needs an *upper* bound: every $C_4$-free graph on $\gg n^{2-c}$ vertices must have an independent set of size $n$. Because $C_4$-free graphs are inherently sparse (Kővári–Sós–Turán / Reiman: $\mathrm{ex}(N,C_4) = O(N^{3/2})$), this is the same "locally-sparse-graphs-have-large-independent-sets" family of arguments used for $R(3,n)$ (triangle-free graphs), not the clique/pseudorandom-density constructions used for $R(4,n)$ lower bounds. The closest *solved* analog in this exact family is Erdős #165 — asymptotic formula for the Ramsey number R(3,k) ($R(3,k)$ asymptotics, still technically open for the constant but order-of-magnitude resolved: Kim [Ki95] lower bound $\Omega(k^2/\log k)$ matches Shearer [Sh83] upper bound $O(k^2/\log k)$, both read on erdosproblems.com/165) and erdos/166 ($R(4,k) \gg k^3/(\log k)^{O(1)}$, PROVED by Mattheus–Verstraëte, *The asymptotics of $r(4,t)$*, Annals of Math. 199 (2024), 919–941, arXiv:2306.04007, read on erdosproblems.com/166) — but both of those concern clique-free (not cycle-free) host graphs, and both push the *lower*-bound side, i.e. the mirror-image difficulty to problem 159's upper-bound need. - No arXiv, OpenAlex, or Semantic Scholar hit for a paper title matching "$C_4$" + "Ramsey" + "$K_n$" that claims any exponent-level (polynomial) improvement of the $n^2/\log^2 n$ Szemerédi upper bound; general cycle-vs-graph upper bound machinery for large fixed cycle length (Erdős–Faudree–Rousseau–Schelp's $r(C_k,H)\le(k-1)m+1$, resolved recently by arXiv:2606.11174, "A general bound on $R(C_k,H)$", which explicitly settles graph-theory-collection problem #34) targets the *opposite* asymptotic regime (long cycle vs. small graph), and gives a bound $O(n^2)$ for $k=4$ with no log saving — weaker than the already-known Szemerédi bound, hence irrelevant to closing this gap.

Attack surface

- Mode: derivation+formalization (this is a genuinely hard open research problem — not literature-resolved, not finite-search). - Concrete first experiment: this is not a problem amenable to a "first experiment" in the finite-search sense (falsifiability is not-finite). The productive first move is a *derivation* experiment: attempt to adapt the "randomly superimposing blow-ups of random graphs" construction of Hefty–Horn–King–Pfender / Campos–Jenssen–Michelen–Pfender–Sahasrabudhe (arXiv:2511.10641) — which pushes past the $G(n,p)$-deletion-threshold barrier for *odd* cycles — to the even case $\ell=4$, checking mechanically (by re-deriving their independent-set/spectral-walk-counting argument in §3–§5 with $\ell=4$ substituted) whether their bipartite-superposition trick produces a $C_4$-free graph beating deletion threshold. Note this targets the (still open, matching) *lower*-bound side; problem 159 itself asks for the *upper*-bound side, which is the harder, structurally different half (see Literature state) and has seen zero polynomial-level attack in the literature found. - Oracle: any claimed proof must be checked against the exact known bounds $n^{3/2}/(\log n)^{3/2}\ll R(C_4,K_n)\ll n^2/(\log n)^2$ (a valid upper-bound proof of $n^{2-c}$ must remain consistent with — i.e. not contradict — the $n^{3/2}$ lower bound) and should be checkable via standard extremal-graph-theory review (Turán/Kővári–Sós–Turán counting, or a computer-checked instance of the deletion/entropy-compression argument for small $n$ as a sanity check, not as a proof). - Feasibility: famous-and-hard. This is a genuine open problem flagged explicitly as unresolved by a paper from 8 months before today's date, by leading Ramsey theorists (Campos, Jenssen, Michelen, Pfender, Sahasrabudhe) who are actively working the adjacent (odd-cycle) case and say the even case resists their new technique. Not in reach without a real new idea; best use of our capacity here is to track the "even cycle" barrier and re-check after any future arXiv update from this group or from Mubayi/Verstraëte/Conlon/Mattheus.

Related

- Erdős #165 — asymptotic formula for the Ramsey number R(3,k) — $R(3,k)$ asymptotic formula (still open on the exact constant, $250 prize); the closest structurally-matched "locally sparse graph ⇒ large independent set" problem (triangle-free vs. $C_4$-free), solved up to constant by Kim [Ki95] (semi-random/nibble method, matching Shearer's [Sh83] entropy-compression upper bound) — the template technique for the "upper bound" direction problem 159 needs. - erdos/166 — $R(4,k)\gg k^3/(\log k)^{O(1)}$, PROVED by Mattheus–Verstraëte (arXiv:2306.04007) via a pseudorandom/finite-geometry ($K_4$-free) construction; same family (fixed small forbidden graph vs. large clique/independent-set) but the mirror-image (lower-bound, clique-free rather than cycle-free) half of the puzzle. - concept/deletion-threshold-barrier — the $G(n,p)$-edge-deletion heuristic that produces Spencer's $k^{1+1/(\ell-2)}$ lower bound and that recent papers (Mubayi–Verstraëte 2024, Conlon–Mattheus–Mubayi–Verstraëte 2024, Campos–Jenssen–Michelen–Pfender–Sahasrabudhe 2025) are learning to beat for odd cycles, via randomly-superimposed-blow-up constructions — not yet beaten for even cycles. - concept/kovari-sos-turan — $\mathrm{ex}(N,C_4)=O(N^{3/2})$, the reason $C_4$-free graphs are forced to be sparse and hence the natural source of both the Spencer lower-bound construction and any future upper-bound argument. - 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 1977 tool for the current-best lower bound. - Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble — Kim's technique for the matching $R(3,n)$ lower bound; the natural (but so far unsuccessful for even cycles) candidate to try to push the $C_4$ *upper*-bound side down. - concept/pseudorandom-finite-geometry-construction — the Mattheus–Verstraëte / Conlon–Mattheus–Mubayi–Verstraëte technique (incidence graphs of generalized polygons, Zarankiewicz-problem connection) that broke the polynomial barrier for $R(4,k)$ and $r(C_5,K_k), r(C_7,K_k)$.