Determine the size Ramsey number $\hat{R}(K_{n,n})$ of the complete bipartite graph (Erdős #560)
Statement
The size Ramsey number $\hat{R}(G)$ is the least number of edges $m$ such that there exists a graph $H$ with $m$ edges for which every $2$-colouring of the edges of $H$ contains a monochromatic copy of $G$. Determine $$\hat{R}(K_{n,n}),$$ where $K_{n,n}$ is the complete bipartite graph with $n$ vertices in each part.
Acceptance. FULLY RESOLVES: determine the order of magnitude of $\hat{R}(K_{n,n})$ — i.e. prove $\hat{R}(K_{n,n})\asymp n^{\alpha}2^n$ with matching upper and lower bounds (in particular, settle the Conlon–Fox–Wigderson conjecture $\hat{R}(K_{n,n})\asymp n^3 2^n$) — with a complete proof. ADVANCES: improve the constant or exponent in the current lower bound ($\tfrac{1}{60}n^2 2^n$) or upper bound ($\tfrac{3}{2}n^3 2^n$), with proof; OR enlarge the regime in which $\hat{R}(K_{s,t})\asymp s^2 t 2^s$ is known toward the diagonal $s=t$, with proof. State the bound proven and confirm it is strictly better than the corresponding bound in the background. Deliver the proof file.
Background
A problem of Erdős, Faudree, Rousseau, and Schelp [EFRS82]; listed as open on erdosproblems.com/560 (fetched 2026-07-13, status 'open'). The known bounds are $$\tfrac{1}{60}n^2 2^n<\hat{R}(K_{n,n})<\tfrac{3}{2}n^3 2^n;$$ the lower bound (valid for $n\geq 6$) is due to Erdős and Rousseau [ErRo93], and the upper bound to Erdős, Faudree, Rousseau, and Schelp [EFRS78b] and independently Nešetřil and Rödl [NeRo78]. Conlon, Fox, and Wigderson [CFW23] proved that $\hat{R}(K_{s,t})\gg s^{2-s/t}t2^s$ for $s\leq t$, and that $\hat{R}(K_{s,t})\asymp s^2 t 2^s$ when $t\gg s\log s$; they conjecture the latter holds for all $s\leq t$, which would give $\hat{R}(K_{n,n})\asymp n^3 2^n$ (matching the exponent of the upper bound). Catalogued as #29 (size Ramsey number of $K_{n,n}$) in the UCSD graphs problem collection. Attacker's tool: this is proof-shaped — a solver brings probabilistic / pseudorandom constructions of economical host graphs $H$ for the upper bound and entropy / counting arguments for the lower bound, possibly formalized in Lean; direct computation is limited because $H$ ranges over all graphs, so the object is not a bounded finite search.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #560 (T. F. Bloom) | website |
| REF-02 | Size Ramsey number of $K_{n,n}$ (#29, UCSD graphs problem collection) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.