Problem 561

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$ .

Let $F_1$ and $F_2$ be the union of stars. More precisely, let $F_1=\cup_{i\leq s} K_{1,n_i}$ and $F_2=\cup_{j\leq t} K_{1,m_j}$ with $n_1\geq \cdots \geq n_s\geq 1$ and $m_1\geq \cdots \geq m_t\geq 1$ . Prove that

\hat{R}(F_1,F_2) = \sum_{2\leq k\leq s+t}l_k

where

l_k=\max\{n_i+m_j-1 : i+j=k\}.

Source: erdosproblems.com/561

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. The formula is proved in special cases and by no source read for all star forests: for the uniform case, all $n_i$ equal and all $m_j$ equal, by [BEFRS78] Theorem 1 (refereed, 1978); under the condition $\binom{l_k}2>\sum_{k\le i\le s+t}l_i$ for all $k$ by Győri and Schelp [GySc02] Theorem 2 (refereed, 2002; the inequality is strict as printed); and, by [DJKR25] (Ars Math. Contemp. 25 (2025), refereed), for $s=1$ and for $s=2$ with $n_1=n_2$ (both when every star of $F_2$ has at least two edges), for all $n_i$ and $m_j$ odd, and for all $n_i$ equal to one odd number with $m_1$ odd and $m_t\ge2$ . A June 2026 arXiv preprint whose first version claimed to "completely confirm" the conjecture withdrew the claim the next day, and its later versions treat only uniform star forests [FLN26] (recorded as a withdrawn claim on its claim page (Fu, Luo and Ni, 2026)); two partial proof claims on the site's claim tab (August and September 2026, both declaring AI assistance, each recorded on a claim page below) have no acceptance evidence. This is a bounded negative finding from the search, not a certificate of openness.

BEFRS78: Burr, S. A., Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., Ramsey-minimal graphs for multiple copies. Nederl. Akad. Wetensch. Proc. Ser. A 81 = Indag. Math. 40 (1978), 187--195, doi:10.1016/S1385-7258(78)80009-2. Theorem 1, p. 188; the conjecture, p. 194. Library home: Burr et al. 1978.
GySc02: Győri, E. and Schelp, R. H., Two-edge colorings of graphs with bounded degree in both colors. Discrete Math. 249 (2002), no. 1--3, 105--110, doi:10.1016/S0012-365X(01)00238-2 (received 29 June 1999, accepted 26 March 2001). Conjecture 1 and Theorem 1, p. 106; Theorem 2, p. 108, with its proof on pp. 108--109. Library home: Győri and Schelp 2002. Theorem 2 prints the condition with the strict inequality the site and [DJKR25] Theorem 1.4 quote; [FLN26] p. 2 restates it with " $\ge$ ", which is not the paper's.
DJKR25: Davoodi, A., Javadi, R., Kamranian, A. and Raeisi, G., On a conjecture of Erdős on size Ramsey number of star forests. Ars Math. Contemp. 25 (2025), no. 2, #P2.09, 10 pp., doi:10.26493/1855-3974.3081.d6c (received 4 May 2023, accepted 10 May 2024, published online 1 April 2025); first posted as arXiv:2111.02065 (3 November 2021). Theorems 1.4 and 2.2--2.6, Lemma 2.1, Conjecture 3.1. Library home: Davoodi 2025.
FLN26: Fu, P., Luo, Z. and Ni, Z., Size Ramsey minimal graphs for uniform star forests. arXiv:2606.04439v3 (4 July 2026); v1 of 3 June 2026 was titled "Size Ramsey number for star forests", v2 of 4 June 2026 "Size Ramsey minimal graphs for star forests". Preprint. Theorem 1.5, p. 3. Library home: Fu 2026.
Zh92: Zhang, K., A note on the size Ramsey number for stars. J. Combin. Math. Combin. Comput. 11 (1992), 209--214. Not held; the multicolor uniform value $\hat r(a_1K_{1,b_1},\dots,a_tK_{1,b_t})=(\sum a_s-t+1)(\sum b_s-t+1)$ is quoted from [FLN26] Theorem 1.4.

Problem 561

Status

Proof claims

Discussion