Determine the Ramsey number $R(C_4,S_n)$ of a 4-cycle versus a star (Erdős #552)
Statement
For graphs $F$ and $G$, let $R(F,G)$ be the least $N$ such that every red/blue colouring of the edges of $K_N$ contains a red copy of $F$ or a blue copy of $G$. Let $C_4$ be the cycle on $4$ vertices and let $S_n=K_{1,n}$ be the star with $n$ edges (on $n+1$ vertices). Determine $R(C_4,S_n)$. In particular, decide whether it is true that for every $c>0$ there are infinitely many $n$ such that $$R(C_4,S_n)\leq n+\sqrt{n}-c.$$
Acceptance. FULLY RESOLVES: either (a) a proof or disproof of the displayed question — prove that for every $c>0$ there are infinitely many $n$ with $R(C_4,S_n)\leq n+\sqrt{n}-c$, or prove no such family exists (e.g. by establishing $R(C_4,S_n)\geq n+\lceil\sqrt{n}\rceil$ for all large $n$, confirming the Zhang–Chen–Cheng conjecture) — a complete written or machine-checkable proof; or (b) a closed-form determination of $R(C_4,S_n)$ valid for all $n$. ADVANCES: extend the set of exactly-known values of $R(C_4,S_n)$ (OEIS A006672) to new $n$ beyond the $q^2\pm t$ ranges of Parsons/[WSZR15]/[ZCC17], each certified by a $C_4$-free witness graph attaining the value together with an exhaustiveness proof that one fewer vertex fails; OR improve the best lower bound (the $6n^{11/40}$ term) or upper bound stated in the background, with proof; OR resolve one of the auxiliary questions on $f(n+1)-f(n)$. Deliver the proof, or the witness graphs plus exhaustiveness certificates plus an extended value table.
Background
A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89], reiterated by Erdős [Er93, p.345; Er94b; Er95; Er96]; listed as open on erdosproblems.com/552 (fetched 2026-07-13, status 'open'). Erdős offered \$100 for a proof or disproof of the displayed second question. Erdős often phrased $R(C_4,S_n)$ equivalently as the minimum degree of a graph forcing a $C_4$ (cf. erdosproblems.com/85). The known bounds are $$n+\sqrt{n}-6n^{11/40}\leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1,$$ the lower bound due to [BEFRS89] and the upper to Parsons [Pa75]; the lower bound is tied to gaps between primes, and under Cramér's conjecture would improve to $n+\sqrt{n}-n^{o(1)}$. Parsons [Pa75] determined $R(C_4,S_n)=n+\lceil\sqrt{n}\rceil$ when $n=q^2+1$ for a prime power $q$, and $R(C_4,S_n)=n+\lceil\sqrt{n}\rceil+1$ when $n=q^2$; both occur infinitely often. Extensions covering $n=q^2\pm t$ for $0\leq t\leq q$ were given by Wu, Sun, Zhang, and Radziszowski [WSZR15] and by Zhang, Chen, and Cheng [ZCC17, ZCC17b]. In every case computed so far $R(C_4,S_n)=n+\lceil\sqrt{n}\rceil+\{0,1\}$, and Zhang, Chen, and Cheng conjecture this holds for all $n\geq 2$ — which would make the answer to the displayed question negative. Related open sub-questions (with $f(n)=R(C_4,S_n)$): is $f(n+1)=f(n)$ infinitely often, and does the set of such $n$ have density $0$? Is $f(n+1)\leq f(n)+2$ for all $n$? OEIS A006672 tabulates values. Attacker's tool: $R(C_4,S_n)$ reduces to a finite extremal question about $C_4$-free graphs (graphs of girth $>4$ with prescribed minimum degree), so exhaustive/orderly generation or SAT/ILP construction of extremal $C_4$-free graphs, combined with algebraic (Erdős–Rényi polarity-graph) constructions, can extend the exact values in A006672 and stress-test the Zhang–Chen–Cheng all-$n$ conjecture.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #552 (T. F. Bloom) | website |
| REF-02 | OEIS A006672 — Ramsey numbers $R(C_4,S_n)$ of the 4-cycle versus stars | website |
| REF-03 | Ramsey numbers of cycles versus stars (#19, UCSD graphs problem collection) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.