Problem 552

Erdős Problem #552: declared status 'open'. Formalized: no. 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?$$ Current best: 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)}$. 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$. Prize: no. OEIS: A006672. Tags: graph theory, ramsey theory.