Problem 558

Let $R_k(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$ -coloured then there is a monochromatic copy of $G$ . Determine

R_k(K_{s,t})

where $K_{s,t}$ is the complete bipartite graph with $s$ vertices in one component and $t$ in the other.

Source: erdosproblems.com/558

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open, in the site's label (OPEN; page last edited 8 February 2026, accessed 2026-09-17). No source determines $R_k(K_{s,t})$ in general, and the search, whose scope the Current assessment records, found no proof claim. The one claim page, Alon, Rónyai and Szabó 1999, settles the instance $s=t=3$ only, so the frontmatter standing derived from it stays open. What is known from the sources read: the exact star values $R_k(K_{1,t})=k(t-1)+1$ when $k$ and $t$ are both even and $k(t-1)+2$ otherwise (Burr and Roberts, quoted by Chung and Graham), the order $\Theta(k^t)$ whenever $s\ge(t-1)!+1$ (Alon, Rónyai and Szabó, J. Combin. Theory Ser. B 76 (1999)), the asymptotics $(1+o(1))k^3$ for $K_{3,3}$ (same paper) and $(1+o(1))k^2$ for $K_{2,2}$ (the site's sentence; Chung and Graham print $k^2-k+1<R_k(K_{2,2})\le k^2+k+1$ for $k-1$ a prime power, from which it follows), the bracket $tk^2+1\le R_k(K_{2,t+1})\le tk^2+k+2$ for $t$ and $k$ powers of one prime (Taranchuk 2024, a preprint, with Chung and Graham's Theorem 2), and Chung and Graham's general bounds, their Theorems 1 and 4. This is a bounded negative finding, not a certificate of openness.

Er81c: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math. 885 (1981), 9--17. Site source key; its pages 9--14 contain no statement about multicolor Ramsey numbers of complete bipartite graphs (p. 13 has only the two-color $r(K(n),C_4)$ , with $C_4=K_{2,2}$ ), and Alon, Rónyai and Szabó cite it, with [ChGr75] and Chung and Graham's 1998 problem book, for having raised the problem. Library home: Erdős 1981.
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. Theorem 1, p. 164; Theorem 1 $'$ , Theorem 2, Corollary 1 and Theorem 3, p. 166; Theorem 4, p. 167; the Concluding Remarks with inequality (10), p. 168; the cyclotomy limit and conjecture (11), p. 169; the paper is in the publisher's open archive. Library home: Chung and Graham 1975; result pages Theorem 1, Theorem 2 and Corollary 1, Theorem 3, Theorem 4, Inequality (10) and Conjecture (11).
ARS99: Alon, N., Rónyai, L. and Szabó, T., Norm-graphs: variations and applications. J. Combin. Theory Ser. B 76 (1999), 280--290, DOI 10.1006/jctb.1999.1906; Theorems 3 and 8, pp. 6--7 of the ten-page author manuscript. Library home: Alon 1999.
Tar24: Taranchuk, V., A new lower bound for the multicolor Ramsey number $r_k(K_{2,t+1})$ . arXiv:2411.14364 (v1 21 November 2024; v2 23 November 2024 with the comment "Result has already been proven by Lazebnik and Mubayi"). Preprint; Theorems 1.2 and 1.3, p. 3. Library home: Taranchuk 2024.
ErGr75: Erdős, P. and Graham, R. L., On partition theorems for finite graphs. Colloq. Math. Soc. János Bolyai 10 (1975), 515--527; the remark on p. 525. Library home: Erdős and Graham 1975.
CGS: Chung, Graham and Spencer, the bounds $ck^3/\log^3k\le R_k(K_{3,3}) \le(2+o(1))k^3$ as cited on [ARS99] p. 5 to [ChGr75]. In [ChGr75] the lower bound is inequality (10), p. 168, derived from Brown's Turán number of $K_{3,3}$ through a probabilistic remark the paper credits to Spencer by personal communication, and the upper bound is Theorem 1 at $s=t=3$ , $2(k+k^{1/3})^3$ . Result page Inequality (10).
AFM00: Axenovich, M., Füredi, Z. and Mubayi, D., On generalized Ramsey theory: the bipartite case. J. Combin. Theory Ser. B 79 (2000), 66--86. Not held; cited on [Tar24] pp. 1--2 for the first verification of the Chung--Graham conjecture at $s=2$ and the bound (1).
LaWo: Lazebnik, F. and Woldar, A. J., the bound $r_k(K_{2,2})\ge k^2+2$ for odd prime powers $k$ , as cited on [Tar24] p. 2. Not held.

Problem 558

Status

Proof claims

Discussion