A problem of Burr, Erd\H{o}s, Faudree, Rousseau, and Schelp \cite{BEFRS89}. Erd\H{o}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 \cite{BEFRS89}, the upper bound is due to Parsons \cite{Pa75}. The lower bound of \cite{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\H{o}s offered \$100 for a proof or disproof of the second question in \cite{BEFRS89}. In \cite{Er96} Erd\H{o}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 \cite{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 \cite{Pa76}, Wu, Sun, Zhang, and Radziszowski \cite{WSZR15}, and Zhang, Chen, and Cheng (\cite{ZCC17} and \cite{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 \cite{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.


References


[BEFRS89] Burr, S. and Erd\"{o}s, P. and Faudree, R. J. and Rousseau, C. C. and Schelp, R. H., Some complete bipartite graph-tree Ramsey numbers. Graph theory in memory of G. A. Dirac (Sandbjerg,
1985) (1989), 79-89.

[Er96] Erd\H{o}s, Paul, Some of my favourite problems on cycles and colourings. Tatra Mt. Math. Publ. (1996), 7-9.

[Pa75] Parsons, T. D., Ramsey graphs and block designs. {I}. Trans. Amer. Math. Soc. (1975), 33--44.

[Pa76] No reference found.


[WSZR15] Wu, Yali and Sun, Yongqi and Zhang, Rui and Radziszowski,
Stanis\l aw P., Ramsey numbers of {$C_4$} versus wheels and stars. Graphs Combin. (2015), 2437--2446.

[ZCC17] Zhang, Xuemei and Chen, Yaojun and Cheng, T. C. Edwin, Some values of {R}amsey numbers for {$C_4$} versus stars. Finite Fields Appl. (2017), 73--85.

[ZCC17b] Zhang, Xuemei and Chen, Yaojun and Cheng, T. C. Edwin, Polarity graphs and {R}amsey numbers for {$C_4$} versus stars. Discrete Math. (2017), 655--660.