Problem 552

Determine the Ramsey number

R(C_4,S_n),

where $S_n=K_{1,n}$ is the star on $n+1$ vertices.

In particular, is it true that, for any $c>0$ , there are infinitely many $n$ such that

R(C_4,S_n)\leq n+\sqrt{n}-c?

Source: erdosproblems.com/552

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. $f(n)$ is known exactly only for special $n$ : all $n\le38$ and $n=67$ , the prime-power families $n=q^2$ and $q^2+1$ , further families of the form $q^2\pm t$ with $0\le t\le q$ , and Zhang, Chen and Cheng's families $n=(q-1)^2+t$ ( $q\ge4$ an even prime power, $t=1,0,-2$ ) and $n=q(q-1)-t$ ( $q\ge5$ an odd prime power, $t=2,4,\ldots,2\lceil q/4\rceil$ ); in general it is known only within the window, for all large $n$ , $n+\lfloor\sqrt n-6n^{\alpha/2}\rfloor<f(n)\le n+\lceil\sqrt n\rceil+1$ , where $\alpha$ is an exponent for gaps between consecutive primes (below $11/20$ in 1989). The refereed determinations have accepted partial claim pages (Parsons 1975, Wu, Sun, Zhang and Radziszowski 2015, Zhang, Chen and Cheng 2017 (Discrete Math.), Zhang, Chen and Cheng 2017 (Finite Fields Appl.)), and Boza's preprint values a claimed one (Boza 2024); none settles the second question. The search, whose scope the Current assessment records, found no proof or disproof of the displayed question and no determination of $f(n)$ for all $n$ . This is a bounded negative finding, not a certificate of openness.

BEFRS89: Burr, S., Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., Some complete bipartite graph-tree Ramsey numbers. Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), Ann. Discrete Math. 41 (1989), 79--89 (the chapter's first-page header says 79--90). Theorem 1, p. 81; Lemma 1.3, p. 81; Theorem 2 and Remark, p. 84; Section 4 (pp. 88--89): the conjecture that for every constant $c'$ infinitely often $f(m)<m+\sqrt m-c'$ , with Erdős's offer of a prize for a proof or disproof, and the questions whether $f(n+1)=f(n)$ infinitely often with density zero and whether $f(n+1)\le f(n)+2$ for all $n$ . Library home: Burr et al. 1989.
Pa75: Parsons, T. D., Ramsey graphs and block designs. I. Trans. Amer. Math. Soc. 209 (1975), 33--44. Theorem 1 and Theorem 2, p. 41. Library home: Parsons 1975 (retrieved from the AMS open back file).
WSZR15: Wu, Yali, Sun, Yongqi, Zhang, Rui and Radziszowski, Stanisław P., Ramsey numbers of $C_4$ versus wheels and stars. Graphs Combin. 31 (2015), no. 6, 2437--2446 (published online 24 January 2015). Theorem 3, on the article's second page (its pages carry no printed folios). Library home: Wu 2015.
Bo24: Boza, L., Exact values and bounds for Ramsey numbers of $C_4$ versus a star graph. arXiv:2409.12770 (v1 19 September 2024; v2 12 June 2026, the version cited, 5 pages); a preprint. Theorem 10 and Remark 12, p. 4. Library home: Boza 2024.
ZCC17: Zhang, Xuemei, Chen, Yaojun and Cheng, T. C. Edwin, Some values of Ramsey numbers for $C_4$ versus stars. Finite Fields Appl. 45 (2017), 73--85. Theorems 6 and 7 and the paragraph after them, p. 75; the question, p. 76. Library home: Zhang and Cheng 2017 (published text).
ZCC17b: Zhang, Xuemei, Chen, Yaojun and Cheng, T. C. Edwin, Polarity graphs and Ramsey numbers for $C_4$ versus stars. Discrete Math. 340 (2017), 655--660. Theorem 4, the restated Theorem 3, the summary of known values with Table 1, and Question 1, p. 656; its family is also restated as Theorem 5 of [ZCC17], p. 75. Library home: Zhang and Cheng 2017 (published text); result page Theorem 4.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 345. Chapter V, problem 7, printed p. 345: the largest minimum degree $f(n)$ of a $C_4$ -free graph on $n$ vertices, the question $f(n+1)\ge f(n)$ , the easy $f(n)<\sqrt n+1$ and the question whether $\liminf f(n)-\sqrt n=-\infty$ ; the survey poses the problem in this minimum-degree form and does not write it as a Ramsey number. Library home: Erdős 1993.
Er94b: Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261--269. Not held.
Er95: Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas 2 (1995), 165--186. Library home: Erdős 1995; its passage on this problem was not read.
Er96: Erdős, Paul, Some of my favourite problems on cycles and colourings. Tatra Mt. Math. Publ. 9 (1996), 7--9. The site's source for the form $R(C_4,S_n)\ge n+\sqrt n-O(1)$ of the question. Not held; reopening condition, the volume 9 listing of the journal's archive or another lawful copy.

Problem 552

Status

Proof claims

Discussion