#552: we didn't find the graph — we proved it has almost nowhere left to hide

The target (erdosproblems.com/552, OPEN). Determine the Ramsey number R(C₄,Sₙ), where Sₙ=K_1,n is the star on n+1 vertices. Write f(n)=R(C₄,K_1,n). Parsons proved f(n) ≤ n+⌈√n⌉+1 in the 1970s, with equality at n=q² and n=q²+1 for prime powers q. Radziszowski's Small Ramsey Numbers, revision #18 (24 April 2026), records that every value f(n) is known for n ≤ 38 — and its Table IVa lists exactly one bracketed entry: f(39) ∈ {46,47}. That is the first open value, and it is where we aimed.

The translation, re-derived rather than inherited. f(n) ≥ N+1 exactly when some graph on N vertices is C₄-free and its complement contains no K_1,n — i.e. every vertex has complement-degree ≤ n−1, i.e. degree ≥ N−n. At n=39, N=46 that reads:

A witness is a C₄-free graph on 46 vertices with minimum degree ≥ 7. It exists ⟺ R(C₄,S₃₉)=47. It doesn't ⟺ R(C₄,S₃₉)=46.

Throughout, "C₄-free" is used in the form every pair of vertices has at most one common neighbour.

1. The witness must be exactly 7-regular — and this needed a proof. The prior write-up asserted 7-regularity. It doesn't follow from the obvious count: the codegree bound Σ_vC(d_v,2) ≤ C(46,2)=1035 happily tolerates degrees up to 13. Here is the argument that does work. In a C₄-free graph N(v) induces a matching (if u∈N(v) had two neighbours w,x∈N(v), then w and x would share both u and v). So each u∈N(v) sends deg(u)−1−t_u edges out to distance-2 vertices, and those sets are pairwise disjoint — a shared vertex plus v is a C₄. Hence n ≥ 1+d+d(δ−1)−2⌊d/2⌋. With δ=7 a degree-8 vertex forces n ≥ 49 > 46. Degree 9 forces 56. So no vertex exceeds 7, and minimum degree 7 makes it regular.

The same count at a 7-regular vertex gives |D₂(v)| = 42−2t(v), so 46 ≥ 50−2t(v) and every vertex lies in 2 or 3 triangles, with exactly 2t(v)−4 vertices at distance ≥ 3.

2. The automorphism group is a 2-group. Let σ be an automorphism of prime order p, with orbits of size p or 1 and 46 = pm+F. For a fixed vertex f, N(f) is σ-invariant, so 7 = pa+b with 0 ≤ b ≤ F−1. That alone kills p = 3, 5, 11, 13, 41, 43. For p = 17, 19, 29, 31, 37 the only solution has a=0, which forces the F fixed points to carry a 7-regular C₄-free graph among themselves — impossible, since F·C(7,2) > C(F,2).

p=7 dies structurally, and prettily. 46 = 6·7+4, and orbit-degree forces (a,b)=(1,0): each of the four fixed points joins exactly one full 7-orbit and no fixed point. Two fixed points on the same orbit would share seven neighbours, so they sit on four distinct orbits; relabel f_i ~ O_i. Then the within-orbit set C_i is empty (else a and a+2c share both a+c and f_i), and |D_ij| ≤ 1 for every j (else d≠d′ make a and a+(d−d′) share a+d as well as f_i). But the degree equation now needs 6 from only five other orbits, each contributing at most 1. Contradiction.

p=23 dies by exhaustion. One 23-orbit plus 23 fixed points is impossible because a fixed point's neighbourhood inside the orbit is invariant, hence empty or all 23. Two 23-orbits reduce — via the abelian lemma below — to two 23-cycles with five cross differences, and we generated and tested all 80,465 normalised cases. None is C₄-free.

3. No witness is vertex-transitive. The only groups of order 46 are Z₄₆ and D₂₃. The circulant half is instant, via a lemma worth stating on its own: no Cayley graph on an abelian group of degree ≥ 3 is C₄-free — pick s∈S; since |S| ≥ 3 and S=−S there is t∈S with t ≠ s,−s, and then 0, s, s+t, t are four distinct vertices forming a C₄. Commutativity simply hands you the square. For the dihedral half we generated and tested all 716,496 symmetric degree-7 connection sets on D₂₃. Zero survivors.

4. Involutions have at most 8 fixed points. If σ swaps u and u′, then σ fixes F pointwise and σ(N(u))=N(u′), so N(u)∩F = N(u′)∩F — meaning every fixed neighbour of u is a common neighbour of u and u′. C₄-freeness therefore gives |N(u)∩F| ≤ 1. Two consequences: each pair attaches to at most one fixed point, which forces e_F ≥ 4F−23 and dies against the extremal values ex(F;C₄) at F = 10, 12, 14; and u keeps ≥ 6 neighbours among the non-fixed vertices, so that induced graph is C₄-free of minimum degree 6 and needs ≥ 31 vertices, giving F ≤ 14. Surviving types: F ∈ {0,2,4,6,8}.

5. The polarity-graph construction is dead. The Erdős–Rényi graph ER₇ is what anyone would try: 57 vertices, C₄-free, 224 edges, eight vertices of degree 7 and forty-nine of degree 8. We need 46 vertices of minimum degree 7, so delete 11 while no surviving degree-7 vertex loses anything and no surviving degree-8 vertex loses two. Counting the edge endpoints leaving the deleted set D, with j of its vertices absolute, gives e_D ≥ 25−j, against ex(11;C₄)=18 — which kills every j ≤ 6 outright. For j = 7 and 8 the absolute points form a conic, hence are pairwise non-adjacent: two adjacent absolute points would make every point of their line absolute, i.e. the conic a line, and no three points of a conic are collinear. The Zarankiewicz bound on what is left then caps e_D at 17 and 14, against the required 18 and 17. Every deletion pattern fails.

6. A spectral surprise. Let K be the 0/1 matrix of codegree-zero pairs. Then identically A² = 6I+J−K, and since A²·1 = 49·1 while J·1 = 46·1, we get K·1 = 3·1: K is a cubic graph. Prettier still, at each vertex its three K-edges split as (7−2t(v)) graph-edges in no triangle plus (2t(v)−4) distance-3 pairs, and those sum to 3 for either value of t(v). On 1^⊥ we have K = 6I−A², so A and K are simultaneously diagonalisable with μ = 6−λ², and K cubic means μ ∈ [−3,3]:

every non-principal eigenvalue satisfies |λ| ∈ [√3, 3]

for a 7-regular graph, where 2√(k−1) = 2√6 ≈ 4.899. Tighter than Ramanujan. It is a severe constraint but not a proof. It does force one thing outright: an integral spectrum would put all 45 non-principal eigenvalues in {±2, ±3}, and with p of them at |λ|=3 and q at |λ|=2 we would need p+q=45 and 9p+4q=273, i.e. 5p=93. Not an integer, so the witness is not an integral graph — in particular not strongly regular. But it does not close the question: we ran the moment problem on the band as a linear program and it is feasible, so the spectrum alone does not close the question. The moments Σλ = −7, Σλ² = 273 and Σλ⁴ = 1785 are unconditional (the last because tr A⁴ = Σ(A²)²_ij = 46·49 + 2·966), and cross-check exactly against tr K = 0 and tr K² = 138. Σλ³ = 6T−343 depends on the triangle count T, which is 46 only if no vertex sits in just two triangles — a step we inherited from the earlier write-up and did not re-verify, so we ran the LP across the whole admissible range 31 ≤ T ≤ 46.

What we got wrong. Worth recording, because it is the exact failure that produces a false positive. For the fixed-point-free case we wrote down a characterisation of the Z₂-voltage lift and it was incomplete — necessary but not sufficient. An adversarial pass checked it over every quotient on 3–6 nodes against every voltage and every internal-edge pattern (9,182,408 configurations) and found 795,512 that satisfy our stated conditions and still contain a C₄. The complete list needs three conditions: the degree-6 nodes independent in Q, every triangle through such a node carrying voltage sum 0, and every 4-cycle of Q carrying voltage sum 1. A nonexistence conclusion from the weak list would still have been sound; an existence claim would not.

Where it stands. Not closed. A witness, if one exists, is a 7-regular C₄-free graph on 46 vertices whose automorphism group is a 2-group in which every involution has at most 8 fixed points; it is not vertex-transitive, admits no automorphism of odd prime order, and does not arise by deletion from ER₇. What is left is the involution cases F ∈ {0,2,4,6,8} and the trivial-automorphism case. Every script, each carrying positive controls its checkers must pass before any verdict is trusted, is in the working repo.