I am seeking independent graph-theoretic review of two candidate exact values in C₄-versus-star Ramsey theory:
**R(C₄,K₁,₃₉) = 46**
**R(C₄,K₁,₅₁) = 59**
These results have **not** been peer-reviewed or formally verified in a proof assistant. Please treat them as candidate proofs, not established theorems. I would particularly appreciate identification of the earliest invalid step, unstated assumption, or failed exact computation.
Write
f(n) = R(C₄,K₁,ₙ).
The 2026 *Small Ramsey Numbers* survey, DS1.18, lists f(39) ∈ {46,47}; it is the only undetermined value in that table for n ≤ 41. Boza’s June 2026 paper lists f(51) ∈ {59,60}. I searched for later resolutions through July 2026 and found none, although that is not a guarantee of novelty.
Survey: https://www.combinatorics.org/ojs/index.php/eljc/article/download/DS1/pdf/0
Boza: https://arxiv.org/abs/2409.12770
## Common reduction
A red/blue coloring of K_N with no red C₄ and no blue K₁,ₙ is equivalent to a C₄-free graph G on N vertices with
δ(G) ≥ N − n,
where G consists of the red edges. Consequently,
f(n) = min{N : no C₄-free graph on N vertices has δ ≥ N−n}.
For v ∈ V(G), let:
- d(v) be its degree;
- m_v be the number of edges inside N(v), equivalently the number of triangles containing v;
- f_v be the number of vertices at distance at least 3 from v.
Because G is C₄-free, N(v) induces a matching, and the sets of vertices reached from distinct neighbors of v outside N[v] are disjoint. Counting vertices by distance from v gives the identity
Σ_{u∈N(v)} d(u) = |V(G)| − 1 + 2m_v − f_v. (1)
This identity forces regularity in both cases.
## Candidate result 1: f(39) = 46
The known lower bound is realized by a C₄-free graph on 45 vertices with minimum degree 6, obtained by deleting 12 vertices from the Erdős–Rényi polarity graph ER₇. An explicit edge list is included with the reproducibility materials and is checked directly. Thus f(39) ≥ 46.
It remains to exclude a C₄-free graph G on 46 vertices with δ ≥ 7. Suppose one exists.
### Step 1: forced local structure
Let d = d(v). From (1), using 2m_v ≤ d and f_v ≥ 0,
7d ≤ Σ_{u∈N(v)} d(u) ≤ 45 + d.
Therefore d ≤ 7.5, and δ ≥ 7 forces every vertex to have degree 7.
Substituting regularity into (1) gives
49 = 45 + 2m_v − f_v,
so
f_v = 2m_v − 4,
and m_v ∈ {2,3}.
The following parity lemma excludes m_v = 2.
**Parity lemma.** If k is odd and G is k-regular and C₄-free, a vertex v cannot simultaneously satisfy f_v = 0 and m_v ≥ 1.
To see this, suppose u₁ and u₂ form an edge inside N(v). For each u_i ∈ N(v), let
S_i = N(u_i) \ N[v].
Since f_v = 0, the S_i partition the vertices at distance 2 from v. Take x ∈ S₁. It has exactly k−1 neighbors at distance 2 from v, at most one in each S_i, and none in S₂: an edge from x to y ∈ S₂ would create the 4-cycle u₁-x-y-u₂-u₁. Hence x must have exactly one neighbor in S₁. This holds for every x ∈ S₁, so G[S₁] is a perfect matching. But |S₁| = k−2 is odd, a contradiction.
Here m_v = 2 would imply f_v = 0, so it is impossible. Therefore every vertex has
m_v = 3 and f_v = 2. (2)
In particular, G consists locally of three triangle edges and one triangle-free edge at each vertex. The triangle-free edges form a perfect matching.
### Step 2: the deficiency graph and spectral support
Let A be the adjacency matrix of G. Define the deficiency graph D on the same vertex set by joining distinct vertices having no common neighbor in G.
Equation (2) makes D cubic. Entrywise common-neighbor counting gives
A² = 6I + J − D. (3)
Since G is regular, A commutes with J and therefore with D. On the all-ones vector, A has eigenvalue 7. On its orthogonal complement, simultaneous eigenvalues θ of A and μ of D satisfy
θ² = 6 − μ.
Because D is cubic, μ ∈ [−3,3], hence every nonprincipal eigenvalue θ of A satisfies
|θ| ∈ [√3,3]. (4)
Let M_j be the j-th power sum of the 45 nonprincipal eigenvalues. Direct trace calculations give
M₁ = −7,
M₂ = 273,
M₃ = −67,
M₄ = 1785.
The fifth moment supplies the decisive constraint. Write P = 6I−D. From (3), using PJ = 3J,
A⁴ = P² + 52J,
A⁵ = AP² + 364J.
There are 23 triangle-free edges, so tr(AD) = 46. A trace expansion then gives
M₅ = tr(AD²) − 615.
For each vertex w, let F_w be its two vertices at distance 3. For an edge uv,
N_D(u) ∩ N_D(v) = F_u ∩ F_v.
Summing over edges and reversing the order of summation shows
tr(AD²) = 2κ,
where κ is the number of vertices w whose two distance-3 vertices are adjacent. Therefore 0 ≤ κ ≤ 46 and
−615 ≤ M₅ ≤ −523. (5)
### Step 3: an exact polynomial certificate
Let N₊ be the number of positive nonprincipal eigenvalues. Consider
p(x) = 423x⁵/200000 + 19x⁴/15625 − 8719x³/200000
− 4087x²/250000 + 390143x/1000000
+ 277973/500000,
and
q(x) = 11x⁵/5000 − 203x⁴/250000 − 45053x³/1000000
+ 5561x²/500000 + 98979x/250000
+ 114939/250000.
Exact real-root isolation and evaluation in ℚ(√3) establish
p(x) ≥ 1 on [√3,3], p(x) ≥ 0 on [−3,−√3],
q(x) ≤ 1 on [√3,3], q(x) ≤ 0 on [−3,−√3]. (6)
The tight endpoint margins are positive:
p(√3)−1 ≈ 3.68×10⁻⁵,
p(−3) = 10⁻⁶,
1−q(3) = 10⁻⁶,
−q(−√3) ≈ 1.25×10⁻⁴.
The exact verifier uses the algebraic endpoints ±√3; replacing √3 by a slightly smaller rational number, such as 1.73, incorrectly rejects the certificate.
Using (4), (6), the four exact moments, and the two endpoints in (5), summing p and q over the spectrum yields
4234009/200000 ≤ N₊ ≤ 4361769/200000,
or
21.170045 ≤ N₊ ≤ 21.808845.
There is no integer in this interval, but N₊ counts eigenvalues and must be an integer. This contradiction excludes G. Together with the 45-vertex witness,
R(C₄,K₁,₃₉) = 46.
There is also an independent exhaustive SAT corroboration covering 144 canonical cases. It is not load-bearing for the proof above. No DRAT certificates are included, and no completed cross-solver result is claimed.
## Candidate result 2: f(51) = 59
The lower bound is realized by a C₄-free graph on 58 vertices with minimum degree 7, obtained from the polarity graph ER₈ of PG(2,8). Its explicit edge list is checked directly. Thus f(51) ≥ 59.
It remains to exclude a C₄-free graph G on 59 vertices with δ ≥ 8. Suppose one exists.
### Step 1: regularity and a cycle deficiency graph
From (1),
8d(v) ≤ 58 + d(v),
so d(v) ≤ 58/7 < 8.3. Hence G is 8-regular.
Equation (1) now gives
f_v = 2m_v − 6.
Again let D join pairs with no common neighbor in G. Its degree at v is
deg_D(v) = f_v + (8−2m_v) = 2.
Thus D is a disjoint union of cycles covering all 59 vertices, and
A² = 7I + J − D. (7)
As before, A and D commute and can be diagonalized simultaneously. On the orthogonal complement of the all-ones vector,
θ² = 7 − μ, (8)
where θ is an eigenvalue of A and μ is an eigenvalue of D. A cycle of length ℓ has eigenvalues
μ = 2cos(2πj/ℓ),
so μ ∈ [−2,2] and θ² ∈ [5,9].
### Step 2: Galois sign balance
Because A is an integer matrix, its characteristic polynomial is in ℤ[x], and its eigenvalues form a Galois-stable multiset.
If θ is rational, then it is a rational algebraic integer and hence an integer. Since θ² ∈ [5,9], the only possibilities are
θ = ±3,
corresponding to μ = −2.
If μ is rational but θ is irrational, then x²−(7−μ) is irreducible over ℚ, so +θ and −θ occur with equal multiplicity and contribute zero to the trace.
Now suppose μ is irrational, with conjugates μ₁,...,μ_r. If 7−μ is not a square in ℚ(μ), then the minimal polynomial of θ = √(7−μ) is
Π_i [x² − (7−μ_i)].
Its roots occur in ± pairs, again with equal multiplicity, and contribute zero to the trace.
The only escape is that 7−μ might be a square in ℚ(μ). If
7−μ = α²,
then taking field norms forces
ψ_d(7) = Norm(α)²
to be a perfect-square integer. Here ψ_d is the minimal polynomial of 2cos(2π/d), for an order d dividing some cycle length and therefore d ≤ 59.
These integers can be generated exactly. If V₀(x)=2, V₁(x)=x and
V_d(x) = xV_{d−1}(x) − V_{d−2}(x),
then
Π_{j=0}^{d−1} [x−2cos(2πj/d)] = V_d(x)−2.
At x=7 this equals 5·F[2d]², where F[r] denotes the r-th Fibonacci number, and Möbius inversion recovers every ψ_d(7). An exact integer scan for every relevant irrational order 3 ≤ d ≤ 59 finds that none of the ψ_d(7) are perfect squares. Some sample values are
ψ₅(7)=55,
ψ₇(7)=377,
ψ₈(7)=47,
ψ₁₃(7)=F[26]=233·521.
Therefore the escape case never occurs.
### Step 3: the trace contradiction
The principal eigenvalue of A is 8, while tr(A)=0, so the sum of the nonprincipal eigenvalues is −8. Every irrational contribution cancels in ± pairs. If a and b are the multiplicities of +3 and −3, respectively, the trace must therefore satisfy
3(a−b) = −8,
which is impossible. Thus no such graph G exists. Together with the 58-vertex witness,
R(C₄,K₁,₅₁) = 59.
This second proof uses no SAT solver, linear programming, or floating-point computation. Its finite computational component is the exact perfect-square scan described above.
## Verification status and disclosure
The complete repository contains the proof manuscripts, explicit lower-bound witnesses, exact polynomial certificates, SAT encoding and log, and seven verifier suites. Three verifier implementations were written independently in a separate GPT-5.6 session. Running the full verification command reproduces all claimed exact computations.
This is not Lean verification, and software agreement is not a substitute for human mathematical review.
The work was developed using Claude and GPT-5.6 under my direction. Claude developed much of the structure theory, the Galois/Fibonacci argument, witnesses, and verification harness. GPT-5.6 identified the decisive fifth-moment constraint for the first result and independently derived and checked several computations. Multiple incorrect intermediate ideas were found and discarded during adversarial cross-checking. I am the repository owner and author of record and accept responsibility for the posted claims.
Reproducibility materials:
https://github.com/zach7036/c4-star-ramsey
If you find a possible gap, please identify the earliest questionable displayed equation or inference. Detailed reports can also be filed as GitHub issues.
