Determine the multicolour Ramsey number $R_k(K_{s,t})$ of complete bipartite graphs (Erdős #558)
Statement
For a graph $G$, let $R_k(G)$ denote the $k$-colour Ramsey number: the least $m$ such that every colouring of the edges of $K_m$ with $k$ colours contains a monochromatic copy of $G$. For fixed positive integers $s\leq t$, determine $$R_k(K_{s,t}),$$ where $K_{s,t}$ is the complete bipartite graph with parts of sizes $s$ and $t$.
Acceptance. FULLY RESOLVES: determine the order of magnitude (or the exact leading asymptotics in $k$) of $R_k(K_{s,t})$ for some pair $(s,t)$ not already settled — i.e. prove $R_k(K_{s,t})\asymp k^{\alpha}$ with matching upper and lower bounds for an $(s,t)$ outside the known cases $K_{2,2}$, $K_{3,3}$, and the regime $s\geq(t-1)!+1$ (for instance $K_{4,4}$) — with proof. ADVANCES: improve the exponent in the Chung–Graham lower or upper bound for some $(s,t)$, with proof; OR compute exact small values of $R_k(K_{2,2})$ (or another $K_{s,t}$) certified by a witness colouring plus an exhaustiveness certificate. Deliver the proof, the improved-bound proof, or the witnesses plus certificates.
Background
A problem of Erdős [Er81c]; listed as open on erdosproblems.com/558 (fetched 2026-07-13, status 'open'). Chung and Graham [ChGr75] proved the general bounds $$(2\pi\sqrt{st})^{\frac{1}{s+t}}\Bigl(\frac{s+t}{e^2}\Bigr)k^{\frac{st-1}{s+t}}\leq R_k(K_{s,t})\leq(t-1)(k+k^{1/s})^s,$$ and determined $R_k(K_{2,2})=(1+o(1))k^2$. Alon, Rónyai, and Szabó [ARS99], using norm-graph constructions, proved $R_k(K_{3,3})=(1+o(1))k^3$ and that $R_k(K_{s,t})\asymp k^t$ whenever $s\geq(t-1)!+1$. The order of magnitude is unknown in general — for instance for $K_{4,4}$. The problem is closely tied to the Zarankiewicz problem and to algebraic (norm / projective) graph constructions. Catalogued as #27 (multicolour Ramsey numbers of complete bipartite graphs) in the UCSD graphs problem collection. Attacker's tool: this is proof-shaped — a solver brings algebraic constructions (norm graphs, projective norm-graphs) for the lower bounds and Kővári–Sós–Turán-type counting for the upper bounds; small cases are accessible via SAT/ILP construction of $k$-colourings avoiding a monochromatic $K_{s,t}$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #558 (T. F. Bloom) | website |
| REF-02 | Multicolour Ramsey numbers of complete bipartite graphs (#27, UCSD graphs problem collection) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.