A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. Erdős often asked about $R(C_4,S_n)$ in the equivalent formulation of asking for a bound on the minimum degree of a graph which would guarantee the existence of a $C_4$ (see [85]).

It is known that\[ n+\sqrt{n}-6n^{11/40} \leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1.\]The lower bound is due to [BEFRS89], the upper bound is due to Parsons [Pa75]. The lower bound of [BEFRS89] is related to gaps between primes, and assuming e.g. Cramer's conjecture on gaps between primes their lower bound would be $n+\sqrt{n}-n^{o(1)}$.

Erdős offered \$100 for a proof or disproof of the second question in [BEFRS89]. In [Er96] Erdős asks (an equivalent formulation of) whether $R(C_4,S_n)\geq n+\sqrt{n}-O(1)$, but says this is probably 'too optimistic'.

They also ask, if $f(n)=R(C_4,S_n)$, whether $f(n+1)=f(n)$ infinitely often, and is the density of such $n$ $0$? Also, is it true that $f(n+1)\leq f(n)+2$ for all $n$? A similar question about an equivalent function is the subject of [85].

Parsons [Pa75] proved that\[R(C_4,S_n)=n+\lceil\sqrt{n}\rceil\]whenever $n=q^2+1$ for a prime power $q$ and\[R(C_4,S_n)=n+\lceil\sqrt{n}\rceil+1\]whenever $n=q^2$ for a prime power $q$ (in particular both equalities occur infinitely often).

This has been extended in various works, all in the cases $n=q^2\pm t$ for some $0\leq t\leq q$ and prime power $q$. We refer to the work of Parsons [Pa76], Wu, Sun, Zhang, and Radziszowski [WSZR15], and Zhang, Chen, and Cheng ([ZCC17] and [ZCC17b]) for a precise description. In every known case\[R(C_4,S_n)=n+\lceil\sqrt{n}\rceil+\{0,1\},\]and Zhang, Chen, and Cheng [ZCC17] speculate whether this is in fact true for all $n\geq 2$ (whence the answer to the question above would be no).

This problem is #19 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 28 October 2025.