Problem 552 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
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?\]

Picture
-------
[Given objects + constraints]  --->  [Count / structure]  --->  [Show bound / existence]

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Benchmarks / known results (from comments)
----------------------------------------
- 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, the upper bound is due
  to Parsons.
- The lower bound of 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)}$.