Is $f(n)$ — the min-degree threshold forcing a $C_4$ — eventually monotonic? (Erdős #85)
Statement
For $n\geq 4$, let $f(n)$ be the least integer such that every graph on $n$ vertices with minimum degree $\geq f(n)$ contains a $4$-cycle $C_4$. Is it true that $f(n+1)\geq f(n)$ for all sufficiently large $n$? A weaker form asks only whether there is a constant $c$ with $f(m)>f(n)-c$ whenever $m>n$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written) that $f(n+1)\geq f(n)$ for all sufficiently large $n$, with an explicit threshold, OR a disproof exhibiting infinitely many $n$ with $f(n+1)<f(n)$ together with a proof. Settling the weaker bounded-dip variant ($f(m)>f(n)-c$ for a fixed $c$ and all $m>n$) resolves that variant and must be clearly flagged as the weaker statement. ADVANCES: extend the exact sequence $f(n)$ (equivalently $R(C_4,K_{1,n})$) to a new record $n$ with a reproducible program and a machine-verifiable exhaustiveness certificate, checking monotonicity over the new range and reporting any dip found; OR prove monotonicity or bounded dips over an explicit infinite subfamily of $n$ with proof; OR sharpen the constant/error term in $f(n)=(1+o(1))\sqrt{n}$ beyond the bound stated in the background. Deliver the proof file, or the search code plus certified value table.
Background
Asked by Erdős [Er93, p.345; Er94b; Er95; Er96]. The function $f$ is a reformulation of the star–quadrilateral Ramsey number $R(C_4,K_{1,n})$: precisely $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})\}$, and the general behaviour of that Ramsey number is erdosproblems.com/552. The bounds there give $f(n)<\sqrt{n}+1$ and $f(n)=(1+o(1))\sqrt{n}$, and it is easy to check $f(4)=2$. The subtlety is that although $f(n)$ grows like $\sqrt{n}$, it need not increase term by term, and proving eventual monotonicity — or even the weaker bounded-dip version, that dips are bounded by a constant $c$ — remains open; the same monotonicity question can be posed with $C_4$ replaced by other fixed graphs. Listed as open on erdosproblems.com/85 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'); a Lean 4 formalisation exists in google-deepmind/formal-conjectures. No Erdős prize is attached. The attacker's tool: exact computation of the values $f(n)$ (equivalently the Ramsey numbers $R(C_4,K_{1,n})$) via constructive extremal-graph search and SAT, extending the sequence far enough to test monotonicity and detect any dip empirically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #85 (T. F. Bloom) | website |
| REF-02 | OEIS A006672 — values of the star–quadrilateral Ramsey function $R(C_4,K_{1,n})$ (related to $f(n)$, Erdős #85) | website |
| REF-03 | Lean 4 formalisation of Erdős #85 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.