Problem 560

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$ -colouring of the edges of $H$ there is 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 component.

Source: erdosproblems.com/560

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open, in the site's label (OPEN; page last edited 18 January 2026, accessed 2026-09-17). No source cited here determines the order of $\hat R(K_{n,n})$ . Checked at statement depth against the sources: $\hat R(K_{n,n})>\frac1{60}n^22^n$ for all $n\ge1$ ([ErRo93] Theorem 1; [CFW23] present the argument for all $t\ge s+2$ in Proposition 2.2 with footnote 1) and $\hat R(K_{n,n})\le4en^32^n$ ([CFW23] Proposition 2.1; the 1978 paper's $b_2n^32^{n-1}$ comes from its Theorem 6 applied at $m=n$ ). The site's constants, $\frac1{60}n^22^n<\hat R(K_{n,n})<\frac32n^32^n$ , are both printed in [ErRo93]: the lower bound is its Theorem 1 for all $n\ge1$ , and the upper bound is its display (1), credited there to [EFRS78b] and derived from a pigeonhole criterion whose parameters work "for all $n\ge6$ "; the site attaches the qualification $n\ge6$ to the lower bound, where the paper has none. The site also credits the upper bound to [NeRo78]; that paper concerns critical Ramsey graphs, the Ramsey graphs minimal under subgraph inclusion, and contains no statement about size Ramsey numbers or $K_{n,n}$ , so its text does not support the credit. Conlon, Fox and Wigderson's Theorem 1.1, $\hat R(K_{s,t})\gg s^{2-s/t}t2^s$ for all $s\le t$ , gives on the diagonal $s=t$ only $\Omega(n^22^n)$ ; their Conjecture 5.1 predicts $\hat R(K_{n,n})=\Theta(n^32^n)$ . The gap is a factor of $n$ . This is a bounded negative finding from the search, not a certificate of openness.

EFRS78b: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., The size Ramsey number. Period. Math. Hungar. 9 (1978), no. 1--2, 145--161, doi:10.1007/BF02018930. Section 8, pp. 160--161; Theorem 6, p. 154. Library home: Erdős et al. 1978.
EFRS82: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., Ramsey numbers for brooms. Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, 1982), Congr. Numer. 35 (1982), 283--293. The site's source key for this problem. Library home: Erdős 1982; it has no passage on size Ramsey numbers.
ErRo93: Erdős, P. and Rousseau, C. C., The size Ramsey number of a complete bipartite graph. Discrete Math. 113 (1993), no. 1--3, 259--262, doi:10.1016/0012-365X(93)90521-T. Display (1) with the criterion (2), p. 259; Lemma 1, p. 260; Theorem 1 with its proof, p. 261. Library home: Erdős and Rousseau 1993; paged at Erdős and Rousseau 1993, Theorem 1 and Erdős and Rousseau 1993, Display (1).
NeRo78: Nešetřil, J. and Rödl, V., The structure of critical Ramsey graphs. Acta Math. Acad. Sci. Hungar. 32 (1978), no. 3--4, 295--300, doi:10.1007/BF01902367. Printed pp. 295--300. Its Theorems 1 and 2 (p. 295) give infinitely many critical Ramsey graphs, Ramsey graphs with no proper subgraph that is a Ramsey graph, for every graph of chromatic number at least 3 and for every 2.5-connected graph; no page mentions size Ramsey numbers or $K_{n,n}$ , and no statement bounds the number of edges of a Ramsey graph. The site credits it, with [EFRS78b], for the upper bound $\frac32n^32^n$ ; the paper's text does not support the credit. Library home: Nešetřil and Rödl 1978.
CFW23: Conlon, D., Fox, J. and Wigderson, Y., Three early problems on size Ramsey numbers. Combinatorica 43 (2023), no. 4, 743--768, doi:10.1007/s00493-023-00034-7 (published online 2 May 2023); arXiv:2111.05420v2 (8 February 2023). Theorem 1.1 and Corollary 1.2 (p. 2), Propositions 2.1 and 2.2 (pp. 3--4), Conjecture 5.1 (p. 19). Library home: Conlon, Fox and Wigderson 2023.
ChGr75: Chung, F. R. K. and Graham, R. L., On multicolor Ramsey numbers for complete bipartite graphs. J. Combin. Theory Ser. B 18 (1975), 164--169, DOI 10.1016/0095-8956(75)90043-X. Cited by [EFRS78b] p. 160 for the ordinary Ramsey bounds $a_1n2^{n/2}\le r(K_{n,n})\le a_2n2^n$ , which enter here only as context: in the paper the lower bound is Theorem 4 (p. 167) at $k=2$ , $s=t=n$ , and the upper bound is the Chvátal--Harary bound $r(K_{t,t};k)\le2tk^t$ that its p. 166 quotes; the paper says nothing about size Ramsey numbers. Library home: Chung and Graham 1975.
Pi02: Pikhurko, O., Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math. 16 (2002), 99--113. Not held; [CFW23] pp. 2 and 4 report its asymptotic formula $\hat r(K_{s,t})=(e/2+o(1))s^2t2^s$ for $t$ sufficiently large in terms of $s$ , which does not cover the diagonal.

Problem 560

Status

Proof claims

Discussion