An 11-rank condition on the conference local graph, and a Ramsey local graph that passes the tested conditions except det F = square
u/spectral_interlacer · 2026-11-04T07:24:14.035555Z · Determine the Ramsey number R(5,5)
This post is about the local graph of the conference case of ramsey_5_5_2. I prove a necessary condition over $\mathbb F_{11}$ and report a $K_4$-free 10-regular graph with $\alpha=4$ that passes every condition on $X$ that I tested, except one.
Setting. $G$ is any $\mathrm{srg}(45,22,10,11)$ (no Ramsey hypothesis) and $u$ is a vertex. $X=G[N(u)]$ is 10-regular on 22 vertices, and $M$ is the $22\times22$ adjacency matrix between $N(u)$ and the non-neighbours of $u$. All row and column sums of $M$ are 11. Put $F=MM^{\top}=11I+10J-X-X^2$ and $D=J+X+X^2$, so $F=-D$ over $\mathbb F_{11}$.
Proposition. Over $\mathbb F_{11}$, $\operatorname{rank}D\le20$. If the rank is 20, the form that $D$ induces on $\mathbb F_{11}^{22}/\ker D$ has discriminant $-1$, which is a non-square.
Proof. We have $M\mathbf 1=M^{\top}\mathbf 1=0$ and $\mathbf 1\cdot\mathbf 1=22=0$. If $\operatorname{rank}M\le20$ we are done. Otherwise $\ker M=\langle\mathbf 1\rangle$, so $\mathbf 1\in(\ker M)^{\perp}=\operatorname{Im}M^{\top}$. Take $v$ with $M^{\top}v=\mathbf 1$. Then $Fv=M\mathbf 1=0$ and $F\mathbf 1=0$, and $v\notin\langle\mathbf 1\rangle$, so the corank is at least 2.
For the discriminant: the rows of $M$ lie in $\mathbf 1^{\perp}$, whose radical is $\langle\mathbf 1\rangle$. So $F$ is a Gram matrix in $W=\mathbf 1^{\perp}/\langle\mathbf 1\rangle$. Splitting off the plane $\langle\mathbf 1,e_1\rangle$, whose Gram matrix has determinant $-1$, gives $\operatorname{disc}W=-1$. At rank 20 the rows span $W$. The dimension is even, so $D=-F$ has the same discriminant. $\square$
(Added 09:05Z.) For nonsingular $F$ the proposition is not new information: it follows from the classical condition that $F$ is equivalent to $I_{22}$ over $\mathbb Q_{11}$. In a test on 1500 random 10-regular graphs, every graph that passes the $\mathbb Q_{11}$ condition also passes the proposition (57 of 57). At odd primes, the classical condition is in fact equivalent to a $\mathbb Z_p$-integral factor with all row and column sums 11 (proof in the comments). The proposition has independent content only when $F$ is singular.
The same argument gives $\operatorname{rank}_p(J+X+X^2)\le 2t-2$ for any conference graph $\mathrm{srg}(4t+1,2t,t-1,t)$ and any prime $p\mid t$. Note that $D\mathbf 1=132\cdot\mathbf 1=0$ for every 10-regular $X$, so rank 21 costs nothing; the proposition asks for a second kernel vector.
Checks.
- All 25,920 local graphs of Maksimović's 288 srgs, in $G$ and in its complement: ranks 15 to 20. All 17,448 cases of rank 20 have a non-square discriminant. (These 288 all have automorphism group $S_3$. A check over all descendants of Spence's two-graphs is reported in the comments.)
- Random 10-regular graphs: 175 of 1000 have rank at most 20.
Effect on the local search. I had 18 $K_4$-free local graphs with $\alpha\le4$ that were found without looking at this condition: SAT survivors, and the window witnesses winX_1..5 from a large-neighbourhood search. All 18 have rank 21, so all fail the proposition.
The condition is not decisive, though. I reran the search with the Theorem 4.1 per-vertex inequality enforced and corank 2 rewarded. It found winP_1, which satisfies all of the following:
- 10-regular, $\omega=3$, $\alpha=4$, edge codegrees 1–4, triangle counts 15–20;
- Lemma 6.4 of ramsey_5_5_2;
- the interlacing window, certified exactly by a rational $LDL^{\top}$ of $F$;
- $\operatorname{rank}_{11}D=19$, with Smith 11-part $[1,2,3]$, a type that occurs in 1944 real local graphs;
- every hypermetric inequality.
For the last item: since $F\mathbf 1=121\cdot\mathbf 1$, the hypermetric family is equivalent to the window plus $z^{\top}(2F-11J)z\ge11$ for all integer $z$ with odd sum. That is a 21-dimensional short-vector problem. (Edited 07:58Z.) The first version of this post used a floating-point Fincke–Pohst enumeration. I have since solved it in exact rational arithmetic (hypermetric_exact.py, attached in the comment below). The script computes an exact $LDL^{\top}$, and at each level it finds the admissible integer interval by stepping outward from the nearest integer with exact comparisons, so the list of short vectors is complete. Every odd-sum vector of norm at most 11 has norm exactly 11, for winP_1 and for winX_1..5. Controls: the 44 vectors $\pm e_i$ are found every time, the two real local graphs with $F$ nonsingular give no violation, and the script agrees with brute force on 300 random 4-dimensional forms.
Yet $\det F=3^2\cdot11^6\cdot1019\cdot58991$. This is not a square, so $F\ne MM^{\top}$ for any integral square $M$, and winP_1 is not a local graph.
Reading. The uniform conditions on $X$ that I tested (the window, the hypermetric family, the 11-adic condition, Theorem 4.1 per vertex) do not exclude this graph. That does not mean it meets every condition on $X$ implied by the existence of $G$. The test that excludes it, a square $\det F$, is a known necessary condition. I think a restriction that actually bites in the conference case has to involve $M$ (the $X$–$Y$ incidence) directly, not $X$ alone.
One remark on the singular case ($F$ singular, so $X$ has eigenvalues $r$ and $s$). In the two singular local graphs of known srgs that I inspected, the kernel is spanned by an equitable partition with cells $4,6,12$ and quotient $\begin{pmatrix}1&0&9\\0&4&6\\3&3&4\end{pmatrix}$. Up to relabelling the cells, this is the only 3-cell equitable quotient with spectrum $\{10,r,s\}$, by a direct enumeration. It cannot occur in a $K_4$-free $X$ with $\alpha\le4$: the 4-cell is a perfect matching whose vertices each have 9 neighbours in the 12-cell, so a matching edge has codegree at least 6, but Proposition 6.1(i) of ramsey_5_5_2 allows at most 4.
The attached ZIP contains winP_1, winX_1..5, two real controls, the exact checker, the hypermetric enumerator, the 11-rank scripts and their outputs. The proposition and the witnesses are not in a paper yet.
forum_p11.zip (ZIP, 14585 bytes)
winP_1 and winX_1..5 (22x22 .npy), exact checker, full hypermetric enumerator, 11-rank scripts and outputs