Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n?

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\,?$$

Equivalent min-degree reformulation (erdos/85): let $f(n)$ be minimal such that every graph on $n$ vertices with $\delta(G)\geq f(n)$ contains a $C_4$. Then $R(C_4,K_{1,n})=\min\{m:f(m)\leq m-n\}$ and $f(n)=\min\{m: m\geq R(C_4,K_{1,n-m})\}$; the bounds below give $f(n)=(1+o(1))\sqrt n$.

Facts

- Prize \$100; status open per erdosproblems.com/552 (site-owner belief, checked 2026-07-02). Marked "cannot be resolved with a finite computation" — the question is about infinitely many $n$, i.e. an asymptotic statement. - Falsifiable: no by finite computation. A "yes" answer would need an infinite constructive family (or existence proof); a "no" answer needs a matching universal lower bound for all large $n$ — neither is a single checkable instance. - Origin: Burr, Erdős, Faudree, Rousseau, Schelp, "Some complete bipartite graph-tree Ramsey numbers" [BEFRS89] (1989); Erdős offered \$100 for the second question there. Restated in [Er93,p.345], [Er94b], [Er95], and [Er96] (where Erdős himself calls a related lower-bound conjecture "probably too optimistic"). - Known bounds (both verified on erdosproblems.com/552, matching the classical papers): $$n+\sqrt n-6n^{11/40}\ \leq\ R(C_4,S_n)\ \leq\ n+\lceil\sqrt n\rceil+1.$$ - Lower bound: BEFRS89 [BEFRS89] — derived using gaps between primes; erdosproblems.com states explicitly that assuming e.g. Cramér's conjecture on prime gaps, the same method would give the much stronger $n+\sqrt n - n^{o(1)}$. - Upper bound: T. D. Parsons, "Ramsey graphs and block designs I", Trans. AMS (1975) [Pa75] — proved via a Kővári–Sós–Turán-style double-counting-of-paths argument bounding the max degree of a $C_4$-free graph. - Exact values on the algebraic subsequence (Parsons [Pa75]): for $q$ a prime power, $$R(C_4,S_n)=n+\lceil\sqrt n\rceil \text{ for } n=q^2+1,\qquad R(C_4,S_n)=n+\lceil\sqrt n\rceil+1 \text{ for } n=q^2,$$ via the Erdős–Rényi/Brown orthogonal-polarity graph of $\mathrm{PG}(2,q)$ (the canonical $C_4$-free extremal construction, concept/polarity-graph). This subsequence recurs infinitely often (once per prime power $q$). - Extended to $n=q^2\pm t$, $0\leq t\leq q$, by Wu, Sun, Zhang, Radziszowski [WSZR15] (2015) and Zhang, Chen, Cheng [ZCC17], [ZCC17b] (2017, via refined polarity-graph counting). In every case computed so far, $R(C_4,S_n)=n+\lceil\sqrt n\rceil+\{0,1\}$ — [ZCC17] speculates this holds for *all* $n\geq 2$, which (if true) directly answers Erdős's second question NO. - Newest result: Luis Boza, "Exact values and bounds for Ramsey numbers of $C_4$ versus a star graph," arXiv:2409.12770 (Sep 2024, v2 Jun 2026) — determines 8 previously-unknown exact/bound values of $f(n)=R(C_4,K_{1,n})$ for $n\leq38$ (e.g. $f(27)=33$, $f(n)=n+7$ for $28\leq n\leq33$ or $n=37$), a new degree-counting theorem ($f(m^2+3)\leq m^2+m+4$ for $m\equiv2\pmod6$, $m\geq8$), and two functional inequalities $f(2n-f(n)+1)\geq n$, $f(f(n)+1)\leq2f(n)-n+2$. Boza's Remark 12 (empirical, from all currently known values): for $2\leq n\leq 82$, $f(n)\geq n+\lceil\sqrt n\rceil$, with no counterexample known for larger $n$ — the entire known-value table is consistent with $R(C_4,S_n)$ *never* dipping below $n+\sqrt n$, i.e. current data leans against Erdős's own question and matches his "too optimistic" hunch in [Er96]. - Companion questions on the same page (unresolved): letting $f(n)=R(C_4,S_n)$, is $f(n+1)=f(n)$ infinitely often (density 0)? Is $f(n+1)\leq f(n)+2$ always? A directly analogous monotonicity question is erdos/85. - No AI-system contribution found: github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems grepped for "552" — zero hits (checked 2026-07-02). - Related problems: erdos/85, erdos/723. - This problem is also #19 in Ramsey Theory in Radziszowski's dynamic-survey-adjacent graph problem collection (linked from erdosproblems.com/552).

Literature state

Not resolved, and the general (all $n$) case is actively worked but only in small-$n$/algebraic-subsequence increments, not asymptotically. Key papers, all read: - [Pa75] Parsons 1975 — upper bound $n+\lceil\sqrt n\rceil+1$, exact values at $n=q^2,q^2+1$. - [BEFRS89] Burr–Erdős–Faudree–Rousseau–Schelp 1989 — origin of the problem, lower bound tied to prime gaps, the \$100 offer. - [WSZR15] Wu–Sun–Zhang–Radziszowski 2015, [ZCC17]/[ZCC17b] Zhang–Chen–Cheng 2017 — extend exact values to $n=q^2\pm t$ via refined polarity-graph counting; conjecture the pattern $n+\lceil\sqrt n\rceil+\{0,1\}$ holds for all $n\geq2$. - arXiv:2409.12770 (Boza, 2024/2026, https://arxiv.org/abs/2409.12770) — most recent, extends the exact-value table to $n\leq38$ and (via new functional inequalities) beyond; its Remark 12 is the freshest empirical evidence, and it supports (does not refute) the "no dip" direction, i.e. weak evidence *against* a positive answer to Erdős's question, though far from a proof either way. - No survey or paper found claims a resolution of the actual open question (whether $R(C_4,S_n)\leq n+\sqrt n-c$ infinitely often for every $c>0$). erdosproblems.com's own disclaimer and the absence of any entry in the teorth/erdosproblems AI-contributions wiki both corroborate this remains genuinely open as of 2026-07-02. - The gap between the proven lower bound ($n+\sqrt n-6n^{11/40}$) and upper bound ($n+\sqrt n+O(1)$) is a $n^{11/40}$-vs-$O(1)$ gap tied to how much can be proven unconditionally about gaps between primes — full resolution of Erdős's question in the "yes" direction along BEFRS89's approach would follow from strong enough prime-gap input (Cramér-type), which is itself wide open (cf. erdos/233, on $\sum d_n^2$).

Attack surface

- Mode: derivation+formalization, bootstrapped by finite-search on the small-$n$ table (not literature-resolution — genuinely open, confirmed above). - Concrete first experiment: extend Boza's (arXiv:2409.12770) exact/bound computation of $f(n)=R(C_4,K_{1,n})$ past $n=82$ using the same machinery — (1) SAT/ILP search for extremal $C_4$-free graphs with the House-of-Graphs database + degree-counting pruning (as Boza did computationally for $n\in\{34,...,39,43\}$) to push exact values further, specifically targeting $n$ just past prime powers ($n=q^2+t$ for $t$ close to $q$, the least-covered regime) to hunt for the first $n$ with $f(n) < n+\lceil\sqrt n\rceil$ (a disproof-by-example of the "no dip" pattern, and evidence toward Erdős's "yes"), or to keep extending the "no counterexample" streak (evidence toward "no"). - Oracle: mechanical for the finite sub-experiment — a candidate graph $G$ on $m$ vertices with $\delta(G)\geq m-n$ and $G\not\supseteq C_4$ shows $f(n)\geq m$ (i.e. $R(C_4,S_n)>m$); $C_4$-freeness and degree are both $O(m^2)$-checkable. But this only ever produces *finitely many* data points — it cannot itself resolve the "infinitely many $n$" question, only build/refute confidence in the conjectured pattern. - Feasibility: honest read — the exact-value table is genuinely extendable by us (tractable SAT/ILP + finite-geometry construction search, same toolkit as Boza 2024), but the actual $100 question is asymptotic and tied to deep unresolved number theory (prime gaps / Cramér-type input) on the "yes" side, or a genuinely new universal extremal-graph argument on the "no" side. Full resolution is not in reach; a incrementally-extended exact table (with the goal of either finding a dip or strengthening Remark 12's pattern) is a well-scoped, citable contribution.

Related

- erdos/85 — the equivalent min-degree formulation $f(n)=\min\{m:\delta\text{-forces-}C_4\}$ and its own open monotonicity conjecture ($f(n+1)\geq f(n)$); erdosproblems.com states explicitly "the behaviour of this Ramsey number more generally is [552]" and vice versa. - erdos/723 — existence of finite projective planes of non-prime-power order (open, Bruck–Ryser-adjacent). This is the deep structural reason exact values of $R(C_4,S_n)$ are only known on/near the prime-power subsequence $n\approx q^2$: the extremal construction (concept/polarity-graph) exists only when a projective plane of the right order exists. - erdos/233 — $\sum_{n\leq N} d_n^2 \ll N(\log N)^2$ for prime gaps $d_n$; same family of prime-gap-strength inputs that BEFRS89's lower bound needs strengthened (Cramér-type) versions of. - concept/polarity-graph — the Erdős–Rényi (1962) / Brown (1966) orthogonal-polarity graph of $\mathrm{PG}(2,q)$: vertices = points, $x\sim y$ iff $x_0y_0+x_1y_1+x_2y_2=0$; the universal $C_4$-free extremal construction underlying every exact value in this problem's literature. - concept/kovari-sos-turan — the double-counting-of-paths-of-length-2 (cherries) technique giving both the classical $\mathrm{ex}(n;C_4)=O(n^{3/2})$ Turán bound and Parsons' $R(C_4,S_n)\leq n+\lceil\sqrt n\rceil+1$ upper bound; the generic upper-bound machine for this whole problem family. - concept/turan-number-c4-free — $\mathrm{ex}(n;C_4)$, exactly determined by Füredi ("New asymptotics for bipartite Turán numbers," JCTA 75(1):141-144, 1996) for $n=q^2+q+1$, $q$ prime power $\geq15$, via a refined local degree-counting argument — structurally the closest fully-worked precedent for "exact extremal value on a prime-power subsequence, general case open," the same shape as Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? itself. - concept/cramer-conjecture — prime-gap strength assumption that would upgrade BEFRS89's lower bound from $n+\sqrt n-6n^{11/40}$ to $n+\sqrt n-n^{o(1)}$ (stated explicitly on erdosproblems.com/552). - SAT/CP-SAT-based finite counterexample search and verification — proposed mechanism (House-of-Graphs + degree-pruned SAT/ILP, as used by Boza 2024 for $n\in\{34,\dots,39,43\}$) for extending the exact-value table.