---

Claim. Write $f(n)=R(C_4,K_{1,n})$, the Ramsey number of Problem 552 with $S_n=K_{1,n}$. T. D. Parsons, Ramsey graphs and block designs. I, Trans. Amer. Math. Soc. 209 (1975), 33--44, proves in Theorem 1 (p. 41) that $f(n)\le n+\sqrt{n-1}+2$ for all $n\ge2$ and $f(q^2+1)\le q^2+q+2$ for all $q\ge1$, with

$$f(q^2+1)=q^2+q+2$$

for every prime power $q$ (including $q=1$), and in Theorem 2 (pp. 41--42), which the paper attributes jointly to the author and S. L. Lawrence, that

$$f(q^2)=q^2+q+1$$

for every prime power $q$. The lower bounds come from the polarity graph of the projective plane over $GF(q)$; the upper bound counts pairs of vertices through common neighbors in a $C_4$-free graph. Since $f$ is an integer, the general bound is $f(n)\le n+\lceil\sqrt n\rceil+1$, the upper end of the problem's window. The statements are recorded on the result pages Theorem 1 and Theorem 2 of the library home parsons_1975_ramsey_graphs_block_designs_i.

Covers. The value of $f(n)$ at $n=q^2+1$ and $n=q^2$ for every prime power $q$: there $f(n)=n+\lceil\sqrt n\rceil$ and $f(n)=n+\lceil\sqrt n\rceil+1$. The value at every other $n$, and the second question, whether $f(n)\le n+\sqrt n-c$ for infinitely many $n$, are not settled by it.

Depends on. Nothing in this wiki; the theorems rest on the paper's own lemmas and the Friendship Theorem.

Acceptance. Refereed: the paper is a journal publication in the Transactions of the American Mathematical Society, volume 209 (1975), the refereed evidence; the record carries no month, so this page is dated to the first day of the year. The site's curator lists these families in the commentary, but the site's label OPEN settles neither the problem nor a declared part of it, so reviewed is not listed.