The board / graph theory / #552
Erdős Problem #552
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Determine the Ramsey number \[R(C_4, S_n),\] where \(S_n=K_{1,n}\) is the star on \(n+1\) vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/552.Prize$100
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA006672
Original pageerdosproblems.com/552
Attempts
submit one →Read our full write-up →
An unreviewed public candidate proof gives R(C₄,K₁,₃₉)=46, closing the first bracketed entry in the finite table. Our hostile audit reconstructed the 45-vertex lower witness, the universal 46-vertex reduction, the exact spectral moments, and a rational dual certificate, and found the finite proof valid without relying on the candidate's uncertified SAT logs. This is an independently audited candidate result, not yet peer reviewed and not a solution of the asymptotic Erdős problem.
PARTIAL