Prove a power saving $R(C_4,K_n)\ll n^{2-c}$ for the 4-cycle vs clique Ramsey number (Erdős #159)
Statement
Let $R(C_4,K_n)$ be the least $N$ such that every red/blue colouring of the edges of the complete graph $K_N$ contains either a red $4$-cycle $C_4$ or a blue clique $K_n$. Prove that there is a constant $c>0$ such that $$R(C_4,K_n)\ll n^{2-c},$$ i.e. that $R(C_4,K_n)=O(n^{2-c})$ for some fixed $c>0$ — a genuine power saving over the near-quadratic bound.
Acceptance. FULLY RESOLVES: either (a) a complete proof that $R(C_4,K_n)\ll n^{2-c}$ for some explicit constant $c>0$, or (b) a disproof — a proof that no such $c$ exists, i.e. $R(C_4,K_n)\gg n^{2-o(1)}$. Machine-checkable (Lean/Coq) preferred, otherwise a full written proof with all steps. ADVANCES, each checkable: improve either published bound — an upper bound strictly below $\frac{n^2}{(\log n)^2}$ (the best stated in the background, and ideally the first power saving), or a lower bound strictly above $\frac{n^{3/2}}{(\log n)^{3/2}}$ (the best stated) — with a complete proof or a reproducible extremal construction plus verification. State the improved bound in words and prove it strictly beats the corresponding background bound. Deliver the proof file, or the construction plus its verification.
Background
Raised by Erdős [Er78, p.34], and repeated in [Er81] and [Er84d]; Erdős offered a prize of $100 (in [Er78]) for a proof or disproof. The current bounds are $\frac{n^{3/2}}{(\log n)^{3/2}}\ll R(C_4,K_n)\ll \frac{n^2}{(\log n)^2}$: the upper bound is due to Szemerédi (recorded in Erdős–Faudree–Rousseau–Schelp [EFRS78]) and the lower bound is due to Spencer [Sp77]. Thus the best known upper bound already improves the trivial $O(n^2)$ by logarithmic factors, but a power saving $n^{2-c}$ — reducing the exponent below $2$ — remains open, as does the reverse possibility that no such $c$ exists. This is #17 in the Ramsey Theory section of the UCSD graphs problem collection. Listed as open on erdosproblems.com/159 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory. Attacker's tool: this is a proof problem — pseudorandom/incidence constructions and refined counting (dependent random choice, spectral and container methods) to push the upper exponent below $2$, or a matching extremal construction forcing $R(C_4,K_n)\gg n^{2-o(1)}$ that would disprove the conjecture.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #159 (T. F. Bloom) | website |
| REF-02 | Ramsey C4 — UCSD graphs problem collection (#17, Ramsey Theory) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.