#552: the missing finite Ramsey value is 46
Update, 11 August 2026. At public Git commit
86a1c505..., an unreviewed candidate proof gives
R(C₄,K1,39) = 46.
We treated the repository as adversarial rather than inheriting its conclusion. A separate standard-library checker reconstructed the 45-vertex lower witness, checked the complete reduction of a hypothetical 46-vertex counterexample, rederived every trace moment, and verified an exact rational polynomial certificate. The audit passed. The candidate's 144 SAT status lines have no checked proof artifacts and are therefore not used in this conclusion.
The proof capsule. A C₄-free graph on 46 vertices with minimum degree at least 7 would first be forced to be 7-regular. A local parity argument then forces every vertex into exactly three edge-disjoint triangles; the seventh incident edge at each vertex forms part of a perfect matching. If A is the adjacency matrix and D joins pairs with no common neighbour, then D is cubic and
A² = 6I + J − D.
Hence every non-principal eigenvalue θ of A lies in [-3,−√3]∪[√3,3]. Their first moments are exactly
(s₀,s₁,s₂,s₃,s₄) = (45,−7,273,−67,1785),
s₅ = T−615, 0 ≤ T ≤ 92.
Put
q(x) = (2x+5)²(3x+5)(4904x²−38072x+85705) / 26468750.
On the negative spectral interval q≤0, while on the positive interval q≤1 because 1−q(x) factors as (3−x)(2x−5)²(14712x²+101560x+210075)/26468750. Substituting the exact moments gives, for every admissible T,
21 < Σq(θ) ≤ N+ ≤ Σ(1−q(−θ)) < 22,
where N+ is the integer number of positive non-principal eigenvalues. That is impossible, so the 46-vertex witness sought below does not exist. The audited 45-vertex graph has minimum degree 6 and is C₄-free, giving the matching lower bound.
Provenance and limits. The lower bound 46 was already established; the
candidate supplies the upper bound. This is not a consequence of Boza's /46 table
cell, which has a wheel-index transcription error. The same order-40 wheel is Zhang's
W39=K₁+C39 under rim-length indexing and W40 under total-order
indexing. A second unreviewed public repository also claims the value using LRAT artifacts, but
its proof archive was not available for this audit. We make no priority claim. Most importantly,
the exact finite value does not settle the asymptotic question in Problem 552, which remains open.
Archived search record, 4 August 2026. The analysis below records how we narrowed the then-open 46-vertex case. Its final status paragraph is superseded by the exact proof above, but the structural reductions and the failed construction routes remain useful.
The historical target (erdosproblems.com/552, OPEN). Determine the Ramsey number R(C₄,Sₙ), where Sₙ=K1,n is the star on n+1 vertices. Write f(n)=R(C₄,K1,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 K1,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(dv,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−tu 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 fi ~ Oi. Then the within-orbit set Ci is empty (else a and a+2c share both a+c and fi), and |Dij| ≤ 1 for every j (else d≠d′ make a and a+(d−d′) share a+d as well as fi). 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 eF ≥ 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 eD ≥ 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 eD 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.
Historical status on 4 August. At that time this was not closed. A witness, if one existed, had to be 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} and the trivial-automorphism case — F = 8 was eliminated on 5 Aug, when its σ-invariant instance came back UNSAT from CaDiCaL after 27.5 hours. That verdict is a solver assertion, not a checked certificate (a proof for a 27-hour UNSAT is impractical to emit); a decorrelated kissat run on the same CNF is the available cross-check. The remaining four instances were still undecided at 27+ hours each. Every script, each carrying positive controls its checkers must pass before any verdict is trusted, is in the working repo. The 11 August exact spectral certificate above now proves that none of these remaining cases can exist.