\documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage{amsmath,amssymb,amsthm} \usepackage[margin=1.05in]{geometry} \usepackage{booktabs,microtype} \usepackage{lmodern,textcomp} \usepackage{listings,xcolor} \usepackage[hidelinks]{hyperref} \hypersetup{pdftitle={Strongly regular graphs on 306, 400, 576, 784 and 1296 vertices from multi-orbit coset fusion and Bush-type Hadamard matrices},pdfauthor={Anton Koval'}} \lstset{basicstyle=\ttfamily\scriptsize,breaklines=true,columns=fullflexible,keepspaces=true, showstringspaces=false,numbers=left,numberstyle=\tiny\color{gray},frame=none,language=Python, commentstyle=\color{gray!60!black},keywordstyle=\bfseries,upquote=false} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{construction}[theorem]{Construction} \newtheorem{computation}[theorem]{Computation} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{question}[theorem]{Question} \newcommand{\F}{\mathbb{F}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\srg}{\mathrm{srg}} \newcommand{\Aut}{\mathrm{Aut}} \newcommand{\code}[1]{\texttt{#1}} \newcommand{\brk}{\allowbreak{}} \emergencystretch=2em \title[Strongly regular graphs on 306, 400, 576, 784 and 1296 vertices]{Strongly regular graphs on $306$, $400$, $576$, $784$ and $1296$ vertices from multi-orbit coset fusion and Bush-type Hadamard matrices} \author{Anton Kova\v{l}} \address{AI Lead, V\'UB banka, Bratislava, Slovakia} \email{akoval@pobox.sk} \date{October 2026. Draft, version 3. Code and data: see the Data availability statement.} \begin{document} \begin{abstract} We construct strongly regular graphs with parameters $(306,55,4,11)$, $(400,171,74,72)$, $(576,253,112,110)$, $(784,351,158,156)$ and $(1296,595,274,272)$, and hence also their complements. All five parameter sets were marked ``?'' (existence unknown) in Brouwer's online table on 10 and 11 October 2026. Three of the graphs were found by a computer search that extends the transitive coset fusion of our earlier papers to groups acting with \emph{two} orbits: the search fuses the orbitals of a group $G$ on $G/H_1\sqcup G/H_2$, screens with tables of marks, solves the exact quadratic equations on the structure constants with a SAT-based solver, and rebuilds every solution from scratch. The groups are $2\times M_{12}$, $5^{1+2}_+{:}4A_5$ and $\mathrm{Sp}(6,2)$. The graphs on $400$, $576$, $784$ and $1296$ vertices come from a short step beyond known constructions. A symmetric Bush-type Hadamard matrix of order $n^2$ whose $n\times n$ blocks have unit diagonal, for instance one of Kharaghani's matrices, defines a strongly regular graph $\Gamma_0$ with the parameters of the Latin square graph $\mathrm{LS}_{n/2+1}(n)$. In $\Gamma_0$ the block rows and the block columns form two orthogonal spreads of Delsarte cliques. Deleting one spread gives the known graphs with $\lambda=\mu$ of Bonato, Holzmann and Kharaghani. By an elementary spread lemma, deleting both gives a strongly regular graph with the parameters of $\mathrm{LS}_{n/2-1}(n)$. Kharaghani's matrices exist for every Hadamard order $n$, so such a graph exists for every $n=4m\ge8$, for example $\srg(1600,741,344,342)$ and $\srg(1936,903,422,420)$. A second source, found by analysing the search hits, is the rule $(a,b)\sim(c,d)$ iff $a\ne c$, $b\ne d$ and $H_{ab}H_{bc}H_{cd}H_{da}=1$ for a symmetric Hadamard matrix $H$. Together the two sources give at least $5$, $7$, $5$ and $6$ pairwise non-isomorphic graphs on $400$, $576$, $784$ and $1296$ vertices. None of the graphs we tested on these four vertex numbers is a Latin square graph, so they say nothing about the orthogonal arrays $\mathrm{OA}(n,n/2-1)$ named in the table. The graph on $306$ vertices has a short description on the $300$ non-square points of the parabolic quadric $Q(4,5)$ together with the six points of a totally singular line; this line is a Delsarte clique. The graph has the parameters of the collinearity graph of a generalized quadrangle $\mathrm{GQ}(5,10)$ but is not geometric, and the same rule over $\F_3$ gives the collinearity graph of $Q(4,3)$. Strong regularity of every graph is also checked by an exact, standalone, standard-library Python program. \end{abstract} \maketitle \section{Introduction} A \emph{strongly regular graph} $\srg(v,k,\lambda,\mu)$ is a $k$-regular graph on $v$ vertices, neither complete nor edgeless, in which two adjacent vertices have exactly $\lambda$ common neighbours and two distinct non-adjacent vertices exactly $\mu$. Equivalently, its adjacency matrix $A$ satisfies $A^2=kI+\lambda A+\mu(J-I-A)$. Brouwer maintains a table of the feasible parameter sets with $v\le1300$ and their status \cite{BrouwerTable}; the book of Brouwer and Van Maldeghem \cite{BvM} contains the same table as of its publication. In earlier work \cite{KovalZ} we found new strongly regular graphs as unions of orbitals of \emph{transitive} permutation groups, i.e.\ as coset graphs. Here we take the next step: a group acting with two orbits. A graph found this way need not be vertex-transitive, and two of our three hits are not. The five parameter sets of this paper are listed in Table~\ref{tab:params}; each row of Brouwer's table covers a parameter set and its complement. \begin{table}[ht] \caption{The parameter sets. ``Comment'' is the comment in \cite{BrouwerTable} on 10 October 2026 (re-read on 11 October 2026), where every row was marked ``?''. The eigenvalues follow from the parameters.}\label{tab:params} \centering\small \begin{tabular}{@{}llll@{}} \toprule parameters & spectrum & complement & comment in \cite{BrouwerTable}\\ \midrule $(306,55,4,11)$ & $55^1\,4^{220}\,(-11)^{85}$ & $(306,250,205,200)$ & none\\ $(400,171,74,72)$ & $171^1\,11^{171}\,(-9)^{228}$ & $(400,228,128,132)$ & $\mathrm{OA}(20,9)$?\\ $(576,253,112,110)$ & $253^1\,13^{253}\,(-11)^{322}$ & $(576,322,178,182)$ & $\mathrm{OA}(24,11)$?\\ $(784,351,158,156)$ & $351^1\,15^{351}\,(-13)^{432}$ & $(784,432,236,240)$ & $\mathrm{OA}(28,13)$?\\ $(1296,595,274,272)$ & $595^1\,19^{595}\,(-17)^{700}$ & $(1296,700,376,380)$ & $\mathrm{OA}(36,17)$?\\ \bottomrule \end{tabular} \end{table} \begin{theorem}\label{thm:main}\leavevmode \begin{enumerate} \item \textup{(Section~\ref{sec:hadamard}.)} Let $K$ be a symmetric Bush-type Hadamard matrix of order $n^2$, $n\ge8$, whose $n\times n$ blocks all have diagonal entries $1$. The graph $\Gamma_0$ with adjacency matrix $\frac12(J+K)-I$ is strongly regular with the parameters of $\mathrm{LS}_{n/2+1}(n)$, the block rows and the block columns are two orthogonal spreads of Delsarte cliques of $\Gamma_0$, and deleting the edges of both spreads gives an \[ \srg\bigl(n^2,\ \tfrac{(n-1)(n-2)}2,\ (\tfrac n2-1)(\tfrac n2-2)+2,\ (\tfrac n2-1)(\tfrac n2-2)\bigr) \] with eigenvalues $1\pm n/2$, the parameters of $\mathrm{LS}_{n/2-1}(n)$. Such matrices $K$ exist for every Hadamard order $n$ (Kharaghani's matrices). For a symmetric Hadamard matrix $H$ of order $n$, the graph $\Gamma(H)$ on $[n]\times[n]$ with $(a,b)\sim(c,d)$ iff $a\neq c$, $b\neq d$ and $H_{ab}H_{bc}H_{cd}H_{da}=1$ is an instance. \item Consequently strongly regular graphs with the parameters of $\mathrm{LS}_{n/2-1}(n)$ exist for every Hadamard order $n\ge8$; in particular there exist strongly regular graphs with parameters $(400,171,74,72)$, $(576,253,112,110)$, $(784,351,158,156)$ and $(1296,595,274,272)$, and, beyond the range of the table, $(1600,741,344,342)$ and $(1936,903,422,420)$. On these four parameter sets of the table there are at least $5$, $7$, $5$ and $6$ pairwise non-isomorphic graphs. None of the graphs listed in Table~\ref{tab:props}, and none of the graphs from Kharaghani's matrices that we built with $n\in\{20,24,28,36\}$, is a Latin square graph. \item \textup{(Section~\ref{sec:306}.)} The graph $\Delta$ of Construction~\ref{con:306}, on the $300$ non-square points of $Q(4,5)$ and the $6$ points of a totally singular line $\ell$, is an $\srg(306,55,4,11)$. Its automorphism group is the stabiliser of $\ell$ in $\mathrm{SO}(5,5)$, of order $60000$, with orbits of lengths $300$ and $6$. It has the parameters of the collinearity graph of a $\mathrm{GQ}(5,10)$, but it is not geometric. \item \textup{(Section~\ref{sec:hits}.)} The three graphs found by the two-orbit search are isomorphic to $\Delta$, to $\Gamma(\mathrm{Pal}_{II}(5)\otimes H_2)$ ($v=576$; $\mathrm{Pal}_{II}(5)$ is Paley's symmetric Hadamard matrix of order $12$, Section~\ref{sec:symorders}, and $H_2$ the Hadamard matrix of order $2$) and to $\Gamma(S-I)$ for the symplectic regular two-graph on $36$ points ($v=1296$). \end{enumerate} \end{theorem} \emph{What is known, and what is new.} The graph $\Gamma_0$ is the classical graph of a regular symmetric Hadamard matrix with constant diagonal \cite{GS70}; its parameters are those of the ``$+$'' rows of Brouwer's table with the comment ``Wallis2 \dots; Goethals-Seidel$(2,n-1)$''. Bush-type matrices are named after Bush \cite{Bush71}, who studied them in connection with finite projective planes of even order. Bush-type matrices of this kind exist for every Hadamard order $n$ by Kharaghani's construction \cite{Kh85,BHK01}. Deleting \emph{one} spread (the block rows) is Lemma~3 of Bonato, Holzmann and Kharaghani \cite{BHK01}; it gives their ``twin'' graphs with $\lambda=\mu$, with the parameters of $\mathrm{LS}_{n/2}(n)$, which are the ``$+$'' rows with the comment ``Wallis \dots; RSHCD$+$''. The spread lemma (Lemma~\ref{lem:spread}) is essentially Proposition~4.1 of Haemers and Tonchev \cite{HT96}. What we add is the observation that the block columns form a second spread, orthogonal to the first, and that deleting it as well gives the parameters of $\mathrm{LS}_{n/2-1}(n)$. As far as we can determine, no published construction gives these parameter sets for $n=20,24,28,36$; Brouwer's table lists only the orthogonal arrays $\mathrm{OA}(n,n/2-1)$, which are not known (Section~\ref{sec:novelty}). \emph{What is proved by hand, and what by computer.} Part (1) is proved by hand in Section~\ref{sec:hadamard}; with Kharaghani's matrices, or with the classical Paley matrices, it gives the existence statements in (2) without a computer. The non-isomorphism statements, the automorphism groups, the statement that no listed graph is a Latin square graph (via an exhaustive count of Delsarte cliques), the strong regularity of $\Delta$, the clique count behind ``not geometric'', and the isomorphisms of (4) are computer results. For $\Delta$ the inclusion of the named group in $\Aut\Delta$ is proved by hand. Every graph of Table~\ref{tab:props} was also checked by the standalone exact program of Appendix~\ref{app:verify}. Table~\ref{tab:status} lists every claim. \subsection*{Conventions} $[n]=\{0,\dots,n-1\}$. $J$ is the all-one matrix, $\mathbf 1$ the all-one vector. For an $\srg(v,k,\lambda,\mu)$ with eigenvalues $k>r>s$, $r,s=\frac12(\lambda-\mu\pm\sqrt{(\lambda-\mu)^2+4(k-\mu)})$; conversely a connected $k$-regular graph with exactly three eigenvalues $k>r>s$ is strongly regular with $\lambda=k+r+s+rs$ and $\mu=k+rs$ \cite[Ch.~1]{BvM}. A clique $C$ has $|C|\le 1-k/s$ (Delsarte bound); a clique attaining it is a \emph{Delsarte clique}, and then every vertex outside $C$ has the same number of neighbours in $C$ \cite[Ch.~1]{BvM}, which by counting edges is $|C|(k-|C|+1)/(v-|C|)$. The Latin square graph $\mathrm{LS}_t(n)$ of an $\mathrm{OA}(n,t)$ is an $\srg(n^2,t(n-1),n-2+(t-1)(t-2),t(t-1))$; its vertex set is covered by $t$ parallel classes of $n$-cliques, which are Delsarte cliques, so every edge lies in a Delsarte clique. $\mathrm{OA}(n,t)$ exists iff $t-2$ mutually orthogonal Latin squares of order $n$ exist. Groups are named as in the ATLAS; TomLib class numbers refer to the GAP package TomLib \cite{TomLib} version 1.2.11 with GAP 4.12.1 \cite{GAP}. \section{Multi-orbit coset fusion}\label{sec:method} \subsection{From one orbit to two} Let $G$ act on a finite set $\Omega$. The orbits of $G$ on $\Omega\times\Omega$ (the \emph{orbitals}) form a coherent configuration, and every $G$-invariant graph on $\Omega$ is a union of \emph{symmetrised} orbitals $O\cup O^{\top}$ avoiding the diagonal. If $G$ is transitive, $\Omega=G/H$ and the configuration is the centraliser algebra of the permutation representation; this is the setting of our earlier searches \cite{KovalZ}, where $G$ ran over the groups of the GAP table-of-marks library TomLib and $H$ over its subgroup classes of index $v$. Here \[ \Omega=G/H_1\ \sqcup\ G/H_2,\qquad |G:H_1|+|G:H_2|=v, \] with $H_1=H_2$ allowed (two copies of the same $G$-set). The configuration now has two fibres, and the orbitals split into four kinds: inside $G/H_1$, inside $G/H_2$, and the two crossing kinds, which are transposes of each other. A union of symmetrised orbitals is $k$-regular iff its valency is $k$ at a point of each fibre. The partition $\{G/H_1,G/H_2\}$ of a $G$-invariant graph is equitable, so its quotient matrix $\left(\begin{smallmatrix}k-d_{12}&d_{12}\\ d_{21}&k-d_{21}\end{smallmatrix}\right)$ has the eigenvalues $k$ and $k-d_{12}-d_{21}$, and the second must be $r$ or $s$ if the graph is strongly regular. With $|G/H_1|d_{12}=|G/H_2|d_{21}$ this gives \begin{equation}\label{eq:equit} d_{12}=\frac{(k-\theta)\,|G:H_2|}{v}\in\Z_{>0}\qquad\text{for some }\theta\in\{r,s\}. \end{equation} \subsection{The pipeline} The search ran over all $414$ tables of marks of TomLib and all pairs of subgroup classes $(H_1,H_2)$ with TomLib class numbers $i\le j$, with $|G:H_i|\ge2$ and $|G:H_1|+|G:H_2|=v$ for a parameter set with $v\le1300$ marked ``?'' in \cite{BrouwerTable} (pages fetched on 10 October 2026). Of the $1393$ such rows, the $1323$ with integral eigenvalues were kept: for conference-type parameters \eqref{eq:equit} has no solution. \begin{enumerate} \item \emph{Marks only.} For each pair, the lengths of the suborbits on $G/H_1\times G/H_1$, $G/H_2\times G/H_2$ and $G/H_1\times G/H_2$ are read off from the products of the corresponding rows of the table of marks (GAP's \code{DecomposedFixedPointVector}), without building any permutation action. Pairs whose action on $\Omega$ is not faithful are dropped, and so are pairs that fail \eqref{eq:equit} for every target. \item \emph{Degrees.} An exact bounded subset-sum test asks whether the suborbit lengths can produce the within-fibre degrees $k-d_{12}$, $k-d_{21}$ and the crossing degree $d_{12}$ simultaneously. \item \emph{Structure constants and CP-SAT.} For the survivors the permutation action on $\Omega$ is built, together with the label matrix of all orbitals and the intersection numbers $p^c_{ab}$ of the configuration. With a $0/1$ variable $x_a$ for each symmetrised orbital, the graph is strongly regular iff \[ \sum_{a,b}x_ax_b\,p^c_{ab}=\lambda x_c+\mu(1-x_c)\quad\text{for every non-diagonal class }c, \] together with the two degree equations. This exact quadratic model (products linearised by auxiliary Boolean variables) is solved with the CP-SAT solver of OR-Tools \cite{ORTools}, one worker per job. \item \emph{Exact rebuild.} Every feasible solution is expanded to the full adjacency matrix and checked with exact integer arithmetic. Each hit was then rebuilt independently in GAP: the group is constructed directly (for instance \code{MathieuGroup(12)} or \code{SymplecticGroup(6,2)}), the subgroup classes are recomputed (by \code{ConjugacyClassesSubgroups} or by descent through maximal subgroups), all orbitals are computed by \code{OrbitsDomain} on pairs, and an exhaustive depth-first search over unions of symmetrised orbitals tests strong regularity directly on the adjacency lists, without the CP-SAT model. \end{enumerate} \emph{Controls.} Before the run on open sets, the same code was run against \emph{known} parameter sets on $15$ TomLib groups ($M_{22}$, $M_{22}.2$, $U_4(2)$, $U_4(2).2$, $A_8$, $S_8$, $L_3(4).2_2$, $U_3(3).2$, $M_{23}$, $M_{12}$, $U_3(5).2$, $A_7$, $S_7$, $L_2(11)$, $M_{11}$): $1477$ pairs, $195$ feasible solutions, all confirmed by the exact check. They include the Schl\"afli graph from $S_6$ on $12+15$ points, the Higman--Sims graph, the McLaughlin graph and known sets with $v=1024$, $1080$, $1225$ and $1288$. \emph{Coverage.} The search is not complete, and nothing in this paper depends on its completeness. Jobs are restricted by the total number of relations of the configuration (rank). At the time of writing, TomLib tables $1$--$140$ were finished up to rank $60$, tables $281$--$414$ up to rank $40$, and tables $141$--$280$ were still running at rank $\le 40$; higher ranks were not searched. The three hits came from tables in the finished parts. The (group, action) pairs searched are recorded in the result files of the run (Data availability). \section{The three hits}\label{sec:hits} \begin{table}[ht] \caption{The three hits of the two-orbit search. ``Classes'' are TomLib class numbers of $H_1,H_2$ in the table of $G$; ``rel.'' is the number of symmetrised non-diagonal orbitals of $G$ on $\Omega$; ``used'' is the number in the union.} \label{tab:hits} \centering\small \begin{tabular}{@{}lllllll@{}} \toprule graph & $G$ (TomLib name) & classes & $|H_1|,\ |H_2|$ & $|\Omega|$ & rel. & used\\ \midrule $\srg(576,253,112,110)$ & \code{2xM12} & $475$, $475$ & $660$, $660$ & $288+288$ & $28$ & $9$ or $8$\\ $\srg(306,55,4,11)$ & \code{5\^{}(1+2)+:4A5} & $98$, $145$ & $100$, $5000$ & $300+6$ & $15$ & $6$\\ $\srg(1296,595,274,272)$ & \code{S6(2)} & $1326$, $1367$ & $1152$, $40320$ & $1260+36$ & $19$ & $9$\\ \bottomrule \end{tabular} \end{table} \subsection{The hit on 576 vertices}\label{sec:hit576} $G=M_{12}\times C_2$ and $H_1=H_2=H\cong L_2(11)$ inside $M_{12}$. $M_{12}$ has two classes of subgroups $L_2(11)$: the maximal one, transitive on the $12$ points, and the one used here, which lies in a point stabiliser $M_{11}$ and has orbits of lengths $11+1$. Intrinsically, let $P$ and $P^*$ be the two inequivalent $12$-point $M_{12}$-sets (interchanged by the outer automorphism). The point stabiliser $M_{11}$ of $p\in P$ is $3$-transitive on $P^*$, and the stabiliser of $(p,q)\in P\times P^*$ is our $H$; so $M_{12}$ acts on $Y=P\times P^*$ with point stabiliser $H$, rank $5$ and subdegrees $1,11,11,55,66$ (the two $11$'s are $\{p\}\times(P^*\setminus q)$ and $(P\setminus p)\times\{q\}$). Hence $G/H=Y\times C_2$ and $\Omega=Y\times C_2\times\{1,2\}$: four copies of $Y$, permuted in pairs by the central involution. $G$ has $40$ orbitals on $\Omega$, giving $28$ symmetrised classes ($9$ inside each copy of $G/H$ and $10$ crossing). Exactly six unions of these classes are $\srg(576,253,112,110)$ (computed twice, by CP-SAT and by the exhaustive GAP rebuild \code{rebuild\_576.g}); they use $9$ or $8$ classes, with crossing degree $d_{12}\in\{132,120\}$, and all six are isomorphic. The maximal $L_2(11)$ gives no solution ($368$ degree-feasible candidates). \subsection{The hit on 306 vertices}\label{sec:hit306} $G=5^{1+2}_+{:}4A_5$, of order $30000$, where $4A_5=4\circ\mathrm{SL}(2,5)$ is the subgroup of $\mathrm{GL}(2,5)$ of matrices of determinant $\pm1$. $H_2$ (order $5000$) is the preimage of a point stabiliser of the action of $G$ on the projective line $\mathrm{PG}(1,5)$ through $4A_5\to A_5\cong L_2(5)$, so $G/H_2$ is $\mathrm{PG}(1,5)$ ($6$ points). $H_1\cong D_{10}\times D_{10}$ has order $100$. There are $15$ symmetrised orbitals and the union of $6$ of them is the graph. The rebuild ran over all four classes of subgroups $D_{10}\times D_{10}$ of index $300$ in $G$ (one acts unfaithfully on $\Omega$) and found exactly one graph. In the language of Section~\ref{sec:306}, $G$ is an index-$2$ subgroup of the stabiliser $L$ of a totally singular line $\ell$ of $Q(4,5)$, $G/H_2$ is the set of points of $\ell$ and $G/H_1$ the set of non-square points; the hit is isomorphic to $\Delta$. \subsection{The hit on 1296 vertices}\label{sec:hit1296} $G=\mathrm{Sp}(6,2)$, $H_2\cong S_8\cong\mathrm O^+(6,2)$ (index $36$; $G/H_2$ is the $2$-transitive action on the $36$ quadratic forms of plus type that polarise to the symplectic form), and $H_1$ of order $1152$ (index $1260$). There are nine classes of subgroups of index $1260$; the one used is the stabiliser of an \emph{ordered pair} of distinct points of the $36$-point action, isomorphic to $S_4\wr S_2$ (the stabiliser in $S_8$ of a partition of $8$ points into two $4$-sets). So $\Omega$ is the set of the $36$ forms together with the $36\cdot35$ ordered pairs of distinct forms. There are $19$ symmetrised orbitals, and the union of $9$ of them is the graph. The rebuild in \code{SymplecticGroup(6,2)}, with the subgroups of index $1260$ found by descent through maximal subgroups, examined all nine classes and found exactly one graph. The nine classes are listed in Table~\ref{tab:1296orb} in the coordinates of Section~\ref{sec:hadamard}. All three rebuilt graphs have the same nauty canonical form as the corresponding CP-SAT hits, and as the graphs built from the explicit constructions of Sections~\ref{sec:hadamard} and~\ref{sec:306} (Section~\ref{sec:verify}). The latter are the descriptions we recommend for rebuilding the graphs; the coset descriptions above are recorded so that the search results can be reproduced. \section{Bush-type Hadamard graphs with two spreads deleted}\label{sec:hadamard} A Hadamard matrix of order $n$ is a $\pm1$ matrix with $HH^{\top}=nI$; for $n>2$, $4\mid n$. It is \emph{normalized} if its first row and first column consist of $1$'s. The graphs on $400$, $576$, $784$ and $1296$ vertices are obtained from a classical strongly regular graph by deleting the edges of two orthogonal spreads of Delsarte cliques. Section~\ref{sec:spreads} proves the general lemma, Section~\ref{sec:bush} applies it to Bush-type Hadamard matrices, Section~\ref{sec:khar} uses Kharaghani's matrices to cover every Hadamard order, and Section~\ref{sec:symrule} treats the rule for symmetric Hadamard matrices that we found first, from the search hits. \subsection{Deleting spreads}\label{sec:spreads} Following Haemers and Tonchev \cite{HT96}, a \emph{spread} of a strongly regular graph is a partition of its vertex set into Delsarte cliques. Two spreads are \emph{orthogonal} if every clique of the one meets every clique of the other in exactly one vertex. \begin{lemma}[spread deletion]\label{lem:spread} Let $\Gamma$ be a primitive $\srg(v,k,\lambda,\mu)$ with eigenvalues $k>r>s$ of multiplicities $1,f,g$, let $\omega=1-k/s$, and let $\mathcal S$ be a spread of $\Gamma$, consisting of $m=v/\omega$ cliques of size $\omega$. Let $\Gamma'$ be $\Gamma$ with the edges inside the cliques of $\mathcal S$ removed. \begin{enumerate} \item $\Gamma'$ has the eigenvalues $k-\omega+1$, $r-\omega+1$, $r+1$, $s+1$ with multiplicities $1$, $m-1$, $f-m+1$, $g$, and $f-m+1>0$. \item $\Gamma'$ is strongly regular if and only if $\omega=r-s$. In that case $\Gamma$ has the parameters of $\mathrm{LS}_t(n)$ with $n=r-s$ and $t=-s$, and $\Gamma'$ has the spectrum of $\mathrm{LS}_{t-1}(n)$: it is a connected strongly regular graph with these parameters if $t\ge3$, and $nK_n$ if $t=2$. \item Let $\mathcal S_1,\dots,\mathcal S_j$ be pairwise orthogonal spreads of a primitive strongly regular graph with the parameters of $\mathrm{LS}_t(n)$, $j0$).\footnote{An elementary argument: if $f=m-1$, the $r$-eigenspace is $\{Nz:z\perp\mathbf 1\}$, with orthogonal projection $E_r=\frac1\omega NN^{\top}-\frac1vJ$, so $A=sI+\frac{k-s}vJ+(r-s)E_r$ lies in the span of $I$, $J$ and $NN^{\top}$. For distinct $x,y$ in one clique of $\mathcal S$ we have $(NN^{\top})_{xx}=(NN^{\top})_{xy}=1$, hence $A_{xy}-A_{xx}=-s$; but $A_{xy}-A_{xx}=1-0=1$, so $s=-1$, contradicting $s\le-2$.} (2) Since $-k/s=\omega-1$, the eigenvalues of (1) are $k'=k+k/s$, $r+k/s$, $r+1$ and $s+1$, with $r+k/s0$, so the degree is a simple eigenvalue, $\Gamma'$ is connected, and a connected regular graph with three eigenvalues is strongly regular. If $t=2$, the eigenvalues are $n-1$ and $-1$, and $\Gamma'=nK_n$. (3) Induction on $j$. By (2), deleting $\mathcal S_1$ gives a graph $\Gamma_1$ with the parameters of $\mathrm{LS}_{t-1}(n)$; for $t-1\ge2$ it is primitive, because its eigenvalues are $n-t+1>0$ and $-(t-1)\le-2$. A clique of $\mathcal S_2$ meets every clique of $\mathcal S_1$ in one vertex, so none of its edges was deleted; it is still a clique of size $n=1+\frac{(t-1)(n-1)}{t-1}$ of $\Gamma_1$, i.e.\ a Delsarte clique. So $\mathcal S_2,\dots, \mathcal S_j$ are pairwise orthogonal spreads of $\Gamma_1$, and $\omega=n=r_1-s_1$ for $\Gamma_1$. \end{proof} \begin{remark} Parts (1) and (2) are essentially \cite[Prop.~4.1]{HT96}: there the spread relation $R_3$ and the relation $R_1$ (adjacent in $\Gamma$ but not in the same clique) form an imprimitive $3$-class association scheme, and the column of $R_1$ in its eigenmatrix lists the eigenvalues of (1). For a genuine Latin square graph a parallel class is a spread, and (2) is the familiar passage from $\mathrm{OA}(n,t)$ to $\mathrm{OA}(n,t-1)$. The point of the lemma is that only the parameters matter: \emph{any} spread in a graph with the parameters of $\mathrm{LS}_t(n)$ can be deleted, whether or not the graph comes from an orthogonal array. \end{remark} \subsection{Bush-type Hadamard matrices}\label{sec:bush} Let $n$ be even. Index the rows and columns of $n^2\times n^2$ matrices by $[n]\times[n]$, and write $K_{ac}$ for the $n\times n$ block with entries $K_{(a,b),(c,d)}$, $b,d\in[n]$. Following \cite{BHK01}, a Hadamard matrix $K$ of order $n^2$ is of \emph{Bush type} if $K_{aa}=J_n$ for all $a$ and $K_{ac}J_n=J_nK_{ac}=0$ for $a\neq c$. Put $E_1=I_n\otimes J_n$ and $E_2=J_n\otimes I_n$, so $(E_1)_{(a,b),(c,d)}=[a=c]$ and $(E_2)_{(a,b),(c,d)}=[b=d]$. \begin{theorem}\label{thm:bush} Let $n\ge4$ be even and let $K$ be a symmetric Bush-type Hadamard matrix of order $n^2$ whose blocks all have unit diagonal: $K_{(a,b),(c,b)}=1$ for all $a,b,c$. \begin{enumerate} \item The graph $\Gamma_0$ with adjacency matrix $A_0=\frac12(J+K)-I$ is a primitive strongly regular graph with the parameters of $\mathrm{LS}_{n/2+1}(n)$ and eigenvalues $\frac n2-1$, $-\frac n2-1$. \item The block rows $R_a=\{a\}\times[n]$ and the block columns $C_b=[n]\times\{b\}$ form two orthogonal spreads of $\Gamma_0$. \item Deleting the spread of block rows gives a strongly regular graph with the parameters of $\mathrm{LS}_{n/2}(n)$ (so $\lambda=\mu$); this is the twin graph of \cite[Lemma~3]{BHK01}. \item Deleting both spreads gives the graph $\Gamma_K$ in which distinct vertices $(a,b)$, $(c,d)$ are adjacent iff $a\neq c$, $b\neq d$ and $K_{(a,b),(c,d)}=1$. Its adjacency matrix is \begin{equation}\label{eq:AK} A=\tfrac12(J+K)-E_1-E_2+I, \end{equation} and for $n\ge6$ it is a connected $\srg\bigl(n^2,\frac{(n-1)(n-2)}2,(\frac n2-1)(\frac n2-2)+2,(\frac n2-1)(\frac n2-2)\bigr)$, with the parameters and the spectrum of $\mathrm{LS}_{n/2-1}(n)$. For $n=4$ it is $4K_4$. \end{enumerate} \end{theorem} \begin{proof} (1) The row of $K$ indexed by $(a,b)$ has sum $n$ (the block $K_{aa}=J_n$ contributes $n$, the other blocks $0$), so $K\mathbf 1=n\mathbf 1$. Since $K$ is symmetric with $K^2=n^2I$, its eigenvalues on $\mathbf 1^{\perp}$ are $\pm n$, and since its diagonal is $1$, $\operatorname{tr}K=n^2$; so the multiplicities on $\mathbf 1^\perp$ are $w_+=\frac{(n+2)(n-1)}2$ and $w_-=\frac{n(n-1)}2$, both positive. Hence $A_0$ has the eigenvalues $k_0=\frac{n^2+n}2-1$ (on $\mathbf 1$), $\frac n2-1$ and $-\frac n2-1$. As $k_0>\frac n2-1\ge1$, $\Gamma_0$ is connected with three eigenvalues, hence strongly regular, and it is primitive since $r_0=\frac n2-1>0$ and $s_0\le-2$. With $r_0-s_0=n$ and $t=-s_0=\frac n2+1$ we have $k_0=t(n-1)$, and the parameters are those of $\mathrm{LS}_{n/2+1}(n)$ (proof of Lemma~\ref{lem:spread}(2)). (2) $K=1$ on $R_a\times R_a$ because $K_{aa}=J$, and on $C_b\times C_b$ by the unit-diagonal hypothesis, so all $R_a$ and $C_b$ are cliques of size $n=1-k_0/s_0$. Each family partitions $[n]\times[n]$, and $R_a\cap C_b=\{(a,b)\}$. (3) and (4) follow from Lemma~\ref{lem:spread} with $t=\frac n2+1$ and $j=1,2$. The adjacency matrix of $\Gamma_K$ is $A_0-(E_1-I)-(E_2-I)$, which is \eqref{eq:AK}. \end{proof} \begin{remark} Without the unit-diagonal hypothesis only the spread of block rows is guaranteed; this is the setting of \cite{BHK01}, where all matrices are constructed from rank-one blocks. Every rank-one block $xx^{\top}$ with $x\in\{\pm1\}^n$ has unit diagonal, so for rank-one Bush-type matrices the second spread is always there. \end{remark} \subsection{Kharaghani's matrices: every Hadamard order}\label{sec:khar} \begin{proposition}[Kharaghani \cite{Kh85}; see {\cite[Thm.~1]{BHK01}}]\label{prop:khar} Let $H$ be a Hadamard matrix of order $n$ whose first column is $\mathbf 1$, with columns $c_1,\dots,c_n$, and put $C_i=c_ic_i^{\top}$. Let $L$ be a symmetric Latin square on the symbols $1,\dots,n$ with constant diagonal $1$. The matrix $K(H,L)$ with blocks $K_{ac}=C_{L(a,c)}$ is a symmetric Bush-type Hadamard matrix of order $n^2$ whose blocks have unit diagonal. \end{proposition} \begin{proof} We include the short proof. $C_i$ is symmetric and $L$ is symmetric, so $K$ is symmetric. $C_1=J$, and for $i\neq1$, $C_iJ=c_i(c_i^{\top}c_1)\mathbf 1^{\top}=0$ since the columns of $H$ are orthogonal; so $K$ is of Bush type. The diagonal of $C_i$ is $c_i\circ c_i=\mathbf 1$. Finally $C_iC_j=c_i(c_i^{\top}c_j)c_j^{\top}=n\delta_{ij}C_i$, so the block $(a,c)$ of $K^2$ is $n\sum_e[L(a,e)=L(e,c)]\,C_{L(a,e)}$. For $a\neq c$ the symbols $L(a,e)$ and $L(e,c)=L(c,e)$ lie in the same column of $L$ and in different rows, so they differ, and the block is $0$. For $a=c$ the row $a$ of $L$ runs through all symbols, so the block is $n\sum_iC_i=nHH^{\top}=n^2I$. \end{proof} Symmetric Latin squares with constant diagonal exist for every even $n$: they are the $1$-factorizations of $K_n$ (for instance the round-robin schedule). Every Hadamard matrix can be brought to the form of Proposition~\ref{prop:khar} by multiplying rows by $-1$. \begin{corollary}\label{cor:every} For every Hadamard order $n\ge8$ there is a strongly regular graph with parameters \[ \bigl(n^2,\ \tfrac{(n-1)(n-2)}2,\ (\tfrac n2-1)(\tfrac n2-2)+2,\ (\tfrac n2-1)(\tfrac n2-2)\bigr), \] the parameters of $\mathrm{LS}_{n/2-1}(n)$, namely $\Gamma_{K(H,L)}$ for any $H$ and $L$ as in Proposition~\ref{prop:khar}. For $n=20,24,28,36$ these are the four sets of Table~\ref{tab:params}; for $n=40$ and $n=44$ they are $(1600,741,344,342)$ and $(1936,903,422,420)$. \end{corollary} \begin{computation}\label{comp:khar} We built $\Gamma_0$, the twin graph and $\Gamma_{K(H,L)}$ for $n=12,16,20,24,28,36,40,44$, from Sylvester, Paley~I, Paley~II and Kronecker-product Hadamard matrices, with the round-robin square and with a randomly relabelled copy of it (and the square $L(a,c)=a\oplus c$ for $n=16$). Every graph was checked by exact integer arithmetic to be strongly regular with the parameters of $\mathrm{LS}_{n/2+1}(n)$, $\mathrm{LS}_{n/2}(n)$ and $\mathrm{LS}_{n/2-1}(n)$ respectively. In particular $\srg(1600,741,344,342)$ was built from $H_2\otimes\mathrm{Pal}_I(19)$ and from $\mathrm{Pal}_{II}(9)\otimes H_2$, and $\srg(1936,903,422,420)$ from $\mathrm{Pal}_I(43)$. ($\mathrm{Pal}_I(q)$ is Paley's first, skew-type, Hadamard matrix of order $q+1$ for a prime power $q\equiv3\pmod4$, and $H_2=\left(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\right)$.) \end{computation} \subsection{The rule for symmetric Hadamard matrices}\label{sec:symrule} The graphs found by the search led us first to the following rule. We now derive it from Theorem~\ref{thm:bush}, and we also keep its original direct proof, which does not need the spread lemma. \begin{construction}\label{con:gamma} Let $H$ be a symmetric Hadamard matrix of order $n$. The graph $\Gamma(H)$ has vertex set $[n]\times[n]$, and distinct vertices $(a,b)$, $(c,d)$ are adjacent iff \[ a\neq c,\qquad b\neq d,\qquad H_{ab}H_{bc}H_{cd}H_{da}=1. \] \end{construction} The product is the product of $H$ around the closed walk $a\to b\to c\to d\to a$, so the relation is symmetric. It does not change if $H$ is replaced by $DHD$ for a diagonal $\pm1$ matrix $D$, by $-H$, or by $PHP^{\top}$ for a permutation matrix $P$ (which relabels $[n]$ on both coordinates). The map $(a,b)\mapsto(b,a)$ is an automorphism of every $\Gamma(H)$: it reverses the walk. \begin{lemma}\label{lem:symbush} Let $H$ be a symmetric Hadamard matrix of order $n$ with rows $h_0,\dots,h_{n-1}$, and put $K_{(a,b),(c,d)}=H_{ab}H_{bc}H_{cd}H_{da}$. Then the block $K_{ac}$ is $x^{(ac)}x^{(ac)\top}$ with $x^{(ac)}=h_a\circ h_c$ (entrywise product), and $K$ is a symmetric Bush-type Hadamard matrix of order $n^2$ whose blocks have unit diagonal. So $\Gamma(H)=\Gamma_K$, and Theorem~\ref{thm:bush} applies. \end{lemma} \begin{proof} $K_{(a,b),(c,d)}=(H_{ab}H_{bc})(H_{ad}H_{dc})=x^{(ac)}_bx^{(ac)}_d$, using $H_{cd}H_{da}=H_{ad}H_{dc}$. So every block is rank-one with unit diagonal, and $K$ is symmetric. $x^{(aa)}=\mathbf 1$ gives $K_{aa}=J$, and for $a\neq c$, $\mathbf 1^{\top}x^{(ac)}=\sum_bH_{ab}H_{bc}=(H^2)_{ac}=0$, so $K_{ac}J=0$. Finally $K^2=n^2I$ is identity (1) in the direct proof below. \end{proof} \begin{theorem}\label{thm:hadamard} Let $H$ be a symmetric Hadamard matrix of order $n\ge8$. Then $\Gamma(H)$ is a connected $\srg\bigl(n^2,\frac{(n-1)(n-2)}2,\lambda,\mu\bigr)$ with \[ \mu=\bigl(\tfrac n2-1\bigr)\bigl(\tfrac n2-2\bigr),\qquad\lambda=\mu+2, \] and spectrum $k^1\,(1+\frac n2)^{f}\,(1-\frac n2)^{g}$ with $f=\frac{(n-1)(n-2)}2$, $g=\frac{(n-1)(n+4)}2$. These are the parameters of the Latin square graph $\mathrm{LS}_{n/2-1}(n)$. \end{theorem} By Lemma~\ref{lem:symbush}, Theorem~\ref{thm:hadamard} is a special case of Theorem~\ref{thm:bush}. The following proof is the one we found first; it computes the spectrum directly and is independent of Lemma~\ref{lem:spread}. \begin{proof}[Direct proof] Index rows and columns of $n^2\times n^2$ matrices by pairs, and put \[ K_{(a,b),(c,d)}=H_{ab}H_{bc}H_{cd}H_{da},\qquad E_1=I_n\otimes J_n,\qquad E_2=J_n\otimes I_n, \] so $(E_1)_{(a,b),(c,d)}=[a=c]$ and $(E_2)_{(a,b),(c,d)}=[b=d]$. $K$ is symmetric. If $a=c$ then $K_{(a,b),(a,d)}=H_{ab}H_{ba}H_{ad}H_{da}=1$ because $H$ is symmetric, and likewise $K=1$ when $b=d$. Hence the entries $[a\ne c][b\ne d][K=1]$ of the adjacency matrix $A$ of $\Gamma(H)$ are those of $\frac12(J+K)$ minus $1$ wherever $a=c$ or $b=d$: \begin{equation}\label{eq:A} A=\tfrac12(J+K)-E_1-E_2+I . \end{equation} We need four identities, each a one-line computation with $H^2=nI$ and $H=H^{\top}$. \begin{enumerate} \item $K^2=n^2I$: \begin{align*} (K^2)_{(a,b),(c,d)}&=\sum_{e,f}H_{ab}H_{be}H_{ef}H_{fa}\,H_{ef}H_{fc}H_{cd}H_{de}\\ &=H_{ab}H_{cd}\sum_{e}H_{be}H_{de}\sum_fH_{fa}H_{fc}=H_{ab}H_{cd}\cdot n\delta_{bd}\cdot n\delta_{ac}, \end{align*} which is $n^2$ if $(a,b)=(c,d)$ and $0$ otherwise. \item $K\mathbf 1=n\mathbf 1$: $\sum_{c,d}H_{ab}H_{bc}H_{cd}H_{da}=H_{ab}\sum_cH_{bc}(H^2)_{ca}=nH_{ab}H_{ba}=n$. \item $KE_1=nE_1$: $(KE_1)_{(a,b),(c,d)}=\sum_fK_{(a,b),(c,f)}=H_{ab}H_{bc}\sum_fH_{cf}H_{fa}=n\delta_{ac}H_{ab}H_{ba} =n\delta_{ac}$. \item $KE_2=nE_2$: $(KE_2)_{(a,b),(c,d)}=\sum_eK_{(a,b),(e,d)}=H_{ab}H_{da}\sum_eH_{be}H_{ed}=n\delta_{bd}H_{ab}H_{ba} =n\delta_{bd}$. \end{enumerate} Transposing (3) and (4) gives $E_1K=nE_1$, $E_2K=nE_2$; also $E_1^2=nE_1$, $E_2^2=nE_2$, $E_1E_2=E_2E_1=J$. So $I,J,K,E_1,E_2$ span a commutative algebra of symmetric matrices, and $\mathbb R^{n^2}$ is the orthogonal sum of $\langle\mathbf 1\rangle$, $U_1=\{x\otimes\mathbf 1:x\perp\mathbf 1\}$, $U_2=\{\mathbf 1\otimes y:y\perp\mathbf 1\}$ and $W=\ker E_1\cap\ker E_2$, of dimensions $1$, $n-1$, $n-1$, $(n-1)^2$, each invariant under all five matrices. By \eqref{eq:A}: \begin{itemize} \item on $\mathbf 1$: $J=n^2$, $K=E_1=E_2=n$, so $A\mathbf 1=\bigl(\frac{n^2+n}2-2n+1\bigr)\mathbf 1=\frac{(n-1)(n-2)}2\mathbf 1$; \item on $U_1$: $J=0$, $E_1=n$, $E_2=0$ and $K=n$ (by (3)), so $A=\frac n2-n+1=1-\frac n2$; the same on $U_2$; \item on $W$: $J=E_1=E_2=0$ and $K=\pm n$ by (1), so $A=1\pm\frac n2$. \end{itemize} The diagonal of $K$ is $1$, so $\operatorname{tr}K=n^2$. Writing $w_\pm$ for the multiplicities of $\pm n$ on $W$, we get $n(1+2(n-1)+w_+-w_-)=n^2$ and $w_++w_-=(n-1)^2$, so $w_+=\frac{(n-1)(n-2)}2$ and $w_-=\frac{n(n-1)}2$. Thus $A$ has eigenvalues $k=\frac{(n-1)(n-2)}2$ (once), $r=1+\frac n2$ ($f=w_+$ times) and $s=1-\frac n2$ ($g=2(n-1)+w_-$ times). For $n\ge8$, $k>r$, so $k$ is a simple eigenvalue of a $k$-regular graph and the graph is connected; with three eigenvalues it is strongly regular, with $\mu=k+rs=\frac{(n-1)(n-2)}2+1-\frac{n^2}4=(\frac n2-1)(\frac n2-2)$ and $\lambda=k+r+s+rs=\mu+2$. For $t=\frac n2-1$ these are $t(n-1)$, $n-2+(t-1)(t-2)$ and $t(t-1)$. \end{proof} \begin{remark}[Relation to known constructions]\label{rem:gs} $K$ is a symmetric Hadamard matrix of order $n^2$ with constant diagonal $1$ and constant row sum $n$ (by (1), (2)), i.e.\ a regular graphical Hadamard matrix, and $K=D(H\otimes H)\Pi D$ with $D=\mathrm{diag}(H_{ab})$ and $\Pi$ the permutation $(a,b)\mapsto(b,a)$. So $\Gamma(H)$ is the graph $\Gamma_0$ of the Goethals--Seidel correspondence \cite{GS70}, with the parameters of $\mathrm{LS}_{n/2+1}(n)$, minus the edges of its two orthogonal spreads of block rows and block columns (a lattice graph $L_2(n)$). In the terminology of Section~\ref{sec:bush}: a known RSHCD$^+$/Bush-type graph with two orthogonal spreads of Delsarte cliques deleted. The construction is therefore a short step from \cite{Kh85,BHK01}, who delete the first spread, and the spread lemma is essentially in \cite{HT96}; what is new is the second deletion and the resulting existence results (Section~\ref{sec:novelty}). The matrices $K$ of Lemma~\ref{lem:symbush} are rank-one Bush-type matrices, but in general not literally of Kharaghani's Latin-square form. In $K(H,L)$ only $n$ distinct blocks occur, the $C_i=c_ic_i^{\top}$, so only $n$ block vectors up to sign; in the matrix of Lemma~\ref{lem:symbush} the block vectors are the $h_a\circ h_c$. Counted up to sign, there are $16=n$ of them for the Sylvester matrix of order $16$ (and indeed $\Gamma(\mathrm{Syl}_{16})$ has the same canonical form as $\Gamma_{K(\mathrm{Syl}_{16},L)}$ for $L(a,c)=a\oplus c$), but $67$, $191$, $134$ and $379$ of them for $\mathrm{Pal}_{II}(5)$, $\mathrm{Pal}_{II}(9)$, $\mathrm{Pal}_{II}(5)\otimes H_2$ and $\mathrm{Pal}_{II}(13)$ (Computation~\ref{comp:noniso} compares the graphs). \end{remark} \subsection{Symmetric Hadamard matrices of the orders needed}\label{sec:symorders} Corollary~\ref{cor:every} already gives existence. The explicit graphs of this paper come from Theorem~\ref{thm:hadamard}, because the search hits are of this form. Symmetric Hadamard matrices are available in every order needed. For a prime power $q\equiv1\pmod 4$ let $Q$ be the Jacobsthal matrix of $\F_q$ ($Q_{xy}=\chi(x-y)$, $\chi$ the quadratic character) and $C=\left(\begin{smallmatrix}0&\mathbf 1^{\top}\\ \mathbf 1&Q\end{smallmatrix}\right)$ the symmetric conference matrix of order $q+1$. Then \[ \mathrm{Pal}_{II}(q)=C\otimes\begin{pmatrix}1&1\\1&-1\end{pmatrix}+I\otimes\begin{pmatrix}1&-1\\-1&-1\end{pmatrix} \] is a symmetric Hadamard matrix of order $2(q+1)$ (Paley's second construction \cite{Paley,CK07}). Kronecker products of symmetric Hadamard matrices are symmetric Hadamard matrices. \begin{corollary}\label{cor:exist} Strongly regular graphs exist with parameters \begin{align*} &(400,171,74,72)&&\text{from }\mathrm{Pal}_{II}(9),\\ &(576,253,112,110)&&\text{from }\mathrm{Pal}_{II}(5)\otimes\left(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\right),\\ &(784,351,158,156)&&\text{from }\mathrm{Pal}_{II}(13),\\ &(1296,595,274,272)&&\text{from }\mathrm{Pal}_{II}(17)\text{ and from the matrices of Proposition~\ref{prop:twograph}}. \end{align*} \end{corollary} Within the range $v\le1300$ of the table, Corollary~\ref{cor:every} applies for $n\in\{8,12,\dots,36\}$. For $n=8,12,16,32$ the parameters $(64,21,8,6)$, $(144,55,22,20)$, $(256,105,44,42)$ and $(1024,465,212,210)$ are marked ``$+$'' in \cite{BrouwerTable}, as Latin square graphs from the known $\mathrm{OA}(n,n/2-1)$. (As a check of the code, $\Gamma$ of the Sylvester matrix of order $8$ and $\Gamma(\mathrm{Pal}_{II}(5))$ are strongly regular with the first two of these parameter sets; we did not compare them with the known graphs.) The four remaining values $n=20,24,28,36$ are exactly the four sets of the corollary. Outside the table, the construction gives $\srg(n^2,\dots)$ for every Hadamard order $n$; for $n=40$ and $44$ no $\mathrm{OA}(n,n/2-1)$, i.e.\ no set of $17$ resp.\ $19$ mutually orthogonal Latin squares, is known: the best known lower bounds for the maximum number $N(n)$ of mutually orthogonal Latin squares of order $n$ are $N(40)\ge7$ and $N(44)\ge5$ \cite[Table~III.3.87]{HCD}. \subsection{Regular two-graphs on 36 points} Let $\mathcal T$ be a regular two-graph on $n$ points with Seidel matrix $S$ (zero diagonal, $\pm1$ elsewhere) and Seidel eigenvalues $\rho_1,\rho_2$, so $S^2=(\rho_1+\rho_2)S-\rho_1\rho_2 I$ and $\rho_1\rho_2=1-n$ \cite{Seidel76,BvM}. If $\rho_1+\rho_2=2$, then $(S-I)^2=S^2-2S+I=nI$: so $H=S-I$ is a symmetric Hadamard matrix with constant diagonal $-1$, and conversely. For $n=36$ these are the regular two-graphs with $\{\rho_1,\rho_2\}=\{7,-5\}$, whose descendants are $\srg(35,16,6,8)$; McKay and Spence \cite{McKS01} found that there are $227$ regular two-graphs on $36$ points. (For regular two-graphs in general see \cite{Seidel76,BvM}; our related uniqueness result for $126$ and $176$ points is \cite{KovalTG}.) \begin{proposition}\label{prop:twograph} Let $H=S-I$ as above, of order $n$, with $n\ge8$. \begin{enumerate} \item The diagonal $\{(a,a)\}$ is a Delsarte clique of $\Gamma(H)$, and every other vertex has exactly $\frac n2-2$ neighbours in it. \item Call a triple $\{a,b,c\}$ of distinct points \emph{odd} if $S_{ab}S_{bc}S_{ca}=-1$ (a two-graph triple for a suitable sign convention). Then $(c,c)\sim(a,b)$ iff $c\notin\{a,b\}$ and $\{a,b,c\}$ is odd; and for $a\neq b$, $c\neq d$: \[ (a,b)\sim(c,d)\iff\begin{cases}\text{never}&\text{if }a=c\text{ or }b=d,\\ \text{always}&\text{if }(c,d)=(b,a),\\ \{a,b,d\}\text{ odd}&\text{if }c=b,\ d\neq a,\\ \{a,b,c\}\text{ odd}&\text{if }d=a,\ c\neq b,\\ \{a,b,c\}\text{ and }\{a,c,d\}\text{ of the same type}&\text{if }\{a,b\}\cap\{c,d\}=\emptyset.\end{cases} \] \item $\Aut\Gamma(H)$ contains $\Aut(\mathcal T)\times\langle(a,b)\mapsto(b,a)\rangle$. \end{enumerate} \end{proposition} \begin{proof} (1) For $a\neq c$: $H_{aa}H_{ac}H_{cc}H_{ca}=(-1)(-1)\cdot1=1$, so the diagonal is a clique of size $n$, and $1-k/s=1+\frac{(n-1)(n-2)/2}{n/2-1}=n$. The number of neighbours of an outside vertex in it is $n(k-n+1)/(n^2-n)=\frac n2-2$. (2) is Construction~\ref{con:gamma} with $H_{xx}=-1$ and $H_{xy}=S_{xy}$ ($x\ne y$), case by case. (3) An automorphism of $\mathcal T$ is a permutation $\pi$ with $PSP^{\top}=DSD$ for a diagonal $\pm1$ matrix $D$; then $PHP^{\top}=DHD$, and $(a,b)\mapsto(\pi a,\pi b)$ preserves $\Gamma(H)$ by the invariances noted after Construction~\ref{con:gamma}. It commutes with the reversal. \end{proof} \emph{The hit.} For the symplectic two-graph take $V=\F_2^6$ with $B(x,y)=x_1y_2+x_2y_1+x_3y_4+x_4y_3+x_5y_6+x_6y_5$ and $f_0(x)=x_1x_2+x_3x_4+x_5x_6$. The quadratic forms of plus type polarising to $B$ are $f_w=f_0+B(w,\cdot)$ with $f_0(w)=0$ ($36$ of them), and $\mathrm{Sp}(6,2)$ acts $2$-transitively on them. Put $S_{ww'}=(-1)^{B(w,w')}$ for $w\neq w'$. A short character-sum computation gives $\sum_{f_0(u)=0}(-1)^{B(w+w',u)}=4(-1)^{B(w,w')}$ for $w\ne w'$ among the $36$ vectors, whence $S^2=2S+35I$: this is the symplectic regular two-graph on $36$ points. By computer, $\Gamma(S-I)$ is isomorphic to the hit of Section~\ref{sec:hit1296}; the diagonal is the orbit of length $36$ (a Delsarte clique, Proposition~\ref{prop:twograph}(1)), and the ordered pairs are the orbit of length $1260$. In the coordinates of the search, a pair $(w,w')$ is the flag $(f_w,p)$ with $p=w+w'$ a non-zero singular vector of $f_w$, and Table~\ref{tab:1296orb} lists the nine symmetrised orbitals of the union with their valencies. \begin{table}[ht] \caption{The orbitals of $\mathrm{Sp}(6,2)$ used by the hit on $1296$ vertices, in the notation of Proposition~\ref{prop:twograph}: points $a,b,c,d$ of the $36$-point set, ``odd'' triples as defined there. Valencies are from a point $(c,c)$ and from a pair $(a,b)$; they sum to $595$ in each column.}\label{tab:1296orb} \centering\small \begin{tabular}{@{}lrr@{}} \toprule relation & from $(c,c)$ & from $(a,b)$\\ \midrule $(c,c)\sim(c',c')$, $c\ne c'$ & $35$ & $0$\\ $(c,c)\sim(a,b)$, $\{a,b,c\}$ odd & $560$ & $16$\\ $(a,b)\sim(b,a)$ & & $1$\\ $(a,b)\sim(b,d)$ with $\{a,b,d\}$ odd, and $(a,b)\sim(c,a)$ with $\{a,b,c\}$ odd & & $32$\\ $\{a,b\}\cap\{c,d\}=\emptyset$; $\{a,b,c\}$, $\{a,c,d\}$ odd; $\{a,b,d\}$, $\{b,c,d\}$ even & & $144$\\ $\{a,b\}\cap\{c,d\}=\emptyset$; all four triples odd & & $96$\\ $\{a,b\}\cap\{c,d\}=\emptyset$; $\{a,b,c\}$, $\{a,c,d\}$ even; $\{a,b,d\}$, $\{b,c,d\}$ odd & & $144$\\ $\{a,b\}\cap\{c,d\}=\emptyset$; all four triples even; $w_a+w_b\neq w_c+w_d$ & & $144$\\ $\{a,b\}\cap\{c,d\}=\emptyset$; $w_a+w_b=w_c+w_d$ (then all four triples are even) & & $18$\\ \midrule total & $595$ & $595$\\ \bottomrule \end{tabular} \end{table} \begin{remark} In Table~\ref{tab:1296orb} the last five rows split the disjoint case of Proposition~\ref{prop:twograph}(2) by the finer invariants of the $\mathrm{Sp}(6,2)$-action (the vector sums $w_a+w_b$, $w_c+w_d$ and the values of $B$ on them); the union of the five rows is exactly ``$\{a,b,c\}$ and $\{a,c,d\}$ of the same type'' (which, by the cocycle identity of a two-graph, is equivalent to ``$\{a,b,d\}$ and $\{b,c,d\}$ of the same type''). The row labels were obtained by computing these invariants and matching them with the orbitals; they are not needed for the construction. \end{remark} \subsection{Several graphs on 1296 vertices} Besides the symplectic two-graph we used three further symmetric Hadamard matrices of order $36$: $H=2E-J$ for the Latin square graphs $E=\mathrm{LS}_3(6)$ of the Cayley tables of $\Z_6$ and of $S_3$ (both $\srg(36,15,6,6)$, so $H^2=36I$ and $H$ has diagonal $-1$), and $\mathrm{Pal}_{II}(17)$, which does not have constant diagonal. \begin{computation}\label{comp:1296} The four graphs $\Gamma(H)$ on $1296$ vertices have automorphism groups of orders $2903040=2\cdot|\mathrm{Sp}(6,2)|$ (symplectic), $3456$ ($\Z_6$), $31104$ ($S_3$) and $19584$ ($\mathrm{Pal}_{II}(17)$), with $2$, $3$, $2$ and $2$ orbits; they are pairwise non-isomorphic. The graphs from $\mathrm{Pal}_{II}(9)$, $\mathrm{Pal}_{II}(5)\otimes H_2$ and $\mathrm{Pal}_{II}(13)$ have automorphism groups of orders $5760$, $760320=8\,|M_{12}|$ and $8736$, with orbits of lengths $40+360$, $576$ and $56+728$. \end{computation} Since the $227$ regular two-graphs on $36$ points give graphs $\Gamma(S-I)$ containing $\Aut(\mathcal T)\times C_2$, it is plausible that most of them give pairwise non-isomorphic graphs; we have not computed this. \subsection{Several graphs on each parameter set}\label{sec:noniso} \begin{computation}\label{comp:noniso} The graphs $\Gamma_{K(H,L)}$ of Computation~\ref{comp:khar} and the graphs $\Gamma(H)$ of this paper were compared by nauty canonical forms (SHA-256 of the output of \code{labelg}, first $8$ hex digits below; $L$ is the round-robin square, $L^*$ the relabelled copy). Within each row all hashes are distinct, so the graphs are pairwise non-isomorphic. \begin{center}\small \begin{tabular}{@{}lll@{}} \toprule $v$ & $\Gamma(H)$, this paper & $\Gamma_{K(H,L)}$ \\ \midrule $400$ & $\mathrm{Pal}_{II}(9)$: \code{b15910f8} & $\mathrm{Pal}_I(19)$: \code{f0ef9bbf}, \code{a535920a}\\ & & $\mathrm{Pal}_{II}(9)$: \code{454baa6c}, \code{a5ff9877}\\ $576$ & $\mathrm{Pal}_{II}(5)\otimes H_2$: \code{077482ff} & $\mathrm{Pal}_I(23)$: \code{0f50c45d}, \code{e737ba94}\\ & & $H_2\otimes\mathrm{Pal}_I(11)$: \code{efcea09d}, \code{0d117300}\\ & & $\mathrm{Pal}_{II}(5)\otimes H_2$: \code{ed973300}, \code{67918c94}\\ $784$ & $\mathrm{Pal}_{II}(13)$: \code{1f455843} & $\mathrm{Pal}_I(27)$: \code{68288734}, \code{57b21e8e}\\ & & $\mathrm{Pal}_{II}(13)$: \code{bf91d851}, \code{e633e123}\\ $1296$ & symplectic: \code{e64993c7}; $\Z_6$: \code{e8ba25bb} & $\mathrm{Pal}_{II}(17)$: \code{38798860}, \code{0f1ea859}\\ & $S_3$: \code{3a31fb59}; $\mathrm{Pal}_{II}(17)$: \code{d4d55b4d} & \\ \bottomrule \end{tabular} \end{center} (In each pair of hashes for $\Gamma_{K(H,L)}$ the first is for $L$, the second for $L^*$.) So there are at least $5$, $7$, $5$ and $6$ pairwise non-isomorphic strongly regular graphs on $400$, $576$, $784$ and $1296$ vertices with the parameters of Table~\ref{tab:params}. In particular the graphs of this paper are not the Kharaghani graphs from the same Hadamard matrices with these squares. The automorphism groups of $\Gamma_{K(\mathrm{Pal}_I(19),L)}$ and $\Gamma_{K(\mathrm{Pal}_I(23),L)}$ have orders $171$ and $253$ (nauty), much smaller than those of $\Gamma(\mathrm{Pal}_{II}(9))$ and $\Gamma(\mathrm{Pal}_{II}(5)\otimes H_2)$ (Table~\ref{tab:props}). \end{computation} These hashes are of a different kind from those in Section~\ref{sec:verify}, which hash \code{dreadnaut}'s canonical adjacency lists; both are complete invariants. We have not tried to decide whether some $\Gamma(H)$ is isomorphic to a graph $\Gamma_{K(H',L')}$ for a Hadamard matrix $H'$ or a Latin square $L'$ not listed here. \subsection{Not Latin square graphs} \begin{lemma}\label{lem:perm} Let $\Gamma_K$ be as in Theorem~\ref{thm:bush}, $n\ge8$ (for instance $\Gamma(H)$). Every clique of size $n$ in $\Gamma_K$ has the form $\{(a,\pi(a)):a\in[n]\}$ for a permutation $\pi$ of $[n]$, and it is a Delsarte clique. If $\Gamma_K$ were a Latin square graph $\mathrm{LS}_{n/2-1}(n)$, it would contain at least $(\frac n2-1)n$ such cliques. \end{lemma} \begin{proof} Two vertices with the same first or the same second coordinate are not adjacent, so a clique meets each row and each column at most once; a clique of size $n$ meets each exactly once. $n=1-k/s$ by Theorem~\ref{thm:bush}. An $\mathrm{LS}_t(n)$ has $t$ parallel classes of $n$ cliques of size $n$. \end{proof} \begin{computation}\label{comp:perm} An exhaustive backtracking search over permutations $\pi$ (\code{props.py permcliques}) finds the following numbers of cliques of size $n$: $0$ for $\Gamma(\mathrm{Pal}_{II}(9))$, $\Gamma(\mathrm{Pal}_{II}(5)\otimes H_2)$, $\Gamma(\mathrm{Pal}_{II}(13))$ and $\Gamma(\mathrm{Pal}_{II}(17))$; $64$, $4$ and $12$ for the symplectic, $\Z_6$ and $S_3$ graphs on $1296$ vertices. All are far below $(\frac n2-1)n$. So none of these seven graphs is a Latin square graph, and none of them implies the existence of an $\mathrm{OA}(n,\frac n2-1)$. For the hits this was checked a second time independently: in the hit on $576$ vertices the edges $(0,5)$, $(0,7)$, $(0,8)$, and in the hit on $1296$ vertices the edge $(0,3)$, lie in no clique of size larger than $12$ resp.\ $18$ (exact branch and bound on the common neighbourhood). The seven counts were reproduced by two further programs written from scratch, the referee's row-by-row backtracking over transversals and an exhaustive depth-first search with forward checking (\code{transv.c}, Data availability). The same program finds no clique of size $n$ at all in any of the graphs $\Gamma_{K(H,L)}$ of Computation~\ref{comp:khar} with $n\in\{20,24,28,36\}$, so these are not Latin square graphs either. \end{computation} \subsection{A third spread?}\label{sec:third} By Lemma~\ref{lem:spread}(3), a third spread of $\Gamma_0$, orthogonal to the block rows and the block columns, could be deleted as well and would give the parameters of $\mathrm{LS}_{n/2-2}(n)$: $(400,152,60,56)$, $(576,230,94,90)$, $(784,324,136,132)$ and $(1296,560,244,240)$, all marked ``?'' in \cite{BrouwerTable}. A clique orthogonal to both spreads meets every block row and block column once, so such a spread consists of $n$ pairwise disjoint cliques of size $n$ of $\Gamma_K$, of the form of Lemma~\ref{lem:perm}. Conversely, by Lemma~\ref{lem:perm} every clique of size $n$ of $\Gamma_K$ is such a transversal, and it is a clique of $\Gamma_0$. So a third spread of $\Gamma_0$ orthogonal to the block rows and the block columns is the same thing as a spread of $\Gamma_K$. We did not find one. \begin{computation}\label{comp:third} \leavevmode \begin{enumerate} \item \emph{Fixed matrices} (\code{transv.c}, all cliques of size $n$, exhaustive, and an exact-cover search for spreads among them). There are no cliques of size $n$, hence no third spread, in $\Gamma_{K(H,L)}$ for $H\in\{\mathrm{Pal}_I(11),\mathrm{Pal}_{II}(5)\}$ ($n=12$), $\mathrm{Pal}_I(19)$, $\mathrm{Pal}_{II}(9)$ ($n=20$), $\mathrm{Pal}_I(23)$, $H_2\otimes\mathrm{Pal}_I(11)$, $\mathrm{Pal}_{II}(5)\otimes H_2$ ($n=24$), $\mathrm{Pal}_I(27)$, $\mathrm{Pal}_{II}(13)$ ($n=28$) and $\mathrm{Pal}_{II}(17)$ ($n=36$), each with the round-robin square and several randomly relabelled copies of it, nor in $\Gamma(H)$ for the symmetric matrices of these orders. In the symplectic, $\Z_6$ and $S_3$ graphs on $1296$ vertices the $64$, $4$ and $12$ cliques of size $36$ do not contain $36$ pairwise disjoint ones (the $64$ cliques of the symplectic graph pairwise meet in $6$, $8$ or $16$ vertices), so there is no spread. As a control, for the Sylvester matrix of order $16$ (with $L(a,c)=a\oplus c$, and by the symmetric rule) there are $448$ cliques of size $16$ and $54208$ spreads among them, and deleting one gives an $\srg(256,90,34,30)$, the parameters of $\mathrm{LS}_6(16)$, as predicted; for $H_2\otimes\mathrm{Pal}_I(7)$ there are none. \item \emph{All Latin squares at once} (SAT, \code{kissat}). For a fixed normalized $H$, a Boolean model encodes a symmetric Latin square $L$ with constant diagonal together with $n$ pairwise disjoint cliques of size $n$ of $\Gamma_{K(H,L)}$, the first of which is fixed to be the diagonal $\{(a,a)\}$ to break symmetry (without loss of generality, see below). Controls: for the Sylvester matrix and $\mathrm{Pal}_I(7)$ of order $8$ the model is satisfiable, and the decoded solutions give $\srg(64,14,6,2)$, the parameters of $\mathrm{LS}_2(8)$, by exact check. For $H=\mathrm{Pal}_I(11)$ ($n=12$) the model is unsatisfiable. The second referee review reproduced this verdict with its own SAT model (different variables and clause generation; unsatisfiable in $11$ seconds, with the same two satisfiable controls). For $H=\mathrm{Pal}_I(19)$ and $H=\mathrm{Pal}_{II}(9)$ ($n=20$) the solver ran for $7200$ seconds each without a verdict. \end{enumerate} \end{computation} Fixing the first transversal to be the diagonal loses nothing. The entry $K(H,L)_{(a,b),(c,d)}=(C_{L(a,c)})_{bd}$ depends on $(a,c)$ only through $L(a,c)$, so for a permutation $s$ of $[n]$ the permutation $(a,b)\mapsto(s(a),b)$ of the vertices, which permutes the block rows, maps $K(H,L)$ to $K(H,L^s)$ with $L^s(s(a),s(c))=L(a,c)$. Here $L^s$ is again a symmetric Latin square with constant diagonal $1$, the map preserves the block rows and the block columns, and for $s=\pi$ it carries a transversal $\{(a,\pi(a))\}$ of a spread to the diagonal. (The identity $PK(H,L)P^{\top}=K(H,L^s)$ was also checked by computer for random $L$ and $s$, \code{wlog\_check.py}.) Since the model ranges over all admissible $L$, the unsatisfiable verdict means: for $H=\mathrm{Pal}_I(11)$ and every symmetric Latin square $L$ with constant diagonal $1$, the graph $\Gamma_0$ of $K(H,L)$ has no third spread orthogonal to the block rows and the block columns, i.e.\ $\Gamma_{K(H,L)}$ has no spread. The same holds for every Kharaghani matrix of order $144$. Every Hadamard matrix of order $12$ is equivalent to $\mathrm{Pal}_I(11)$ (see \cite{CK07}), and the automorphism group of $\mathrm{Pal}_I(11)$ is transitive on its columns (it induces $M_{12}$ on them). So a Hadamard matrix $H'$ of order $12$ with first column $\mathbf 1$ arises from $\mathrm{Pal}_I(11)$ by re-normalising at some column $j$ (multiplying rows by $-1$ so that column $j$ becomes $\mathbf 1$; this absorbs the row signings), then permuting rows, negating columns, and permuting columns so that column $j$ comes first. Column negations do not change the matrices $c_ic_i^{\top}$, row permutations of $H$ permute the block columns, and column permutations relabel the symbols of $L$; so $\Gamma_{K(H',L)}$ is isomorphic, by a map preserving block rows and block columns, to $\Gamma_{K(N_j,L')}$ for an admissible $L'$, where $N_j$ is $\mathrm{Pal}_I(11)$ re-normalised at column $j$. By the transitivity on columns, $N_j$ arises in the same way from the matrix normalised at the first column, which is the one used in the model. The timeouts at $n=20$ support nothing either way. So the rows of $\mathrm{LS}_{n/2-2}(n)$ type, and the further ones that would need four or more spreads, remain open. \section{The graph on 306 vertices}\label{sec:306} We use the setting of the construction of $\srg(300,69,18,15)$ in \cite[\S3]{KovalZ}. On $\F_5^5$ let \[ Q(y)=y_0^2+y_1y_2+y_3y_4,\qquad B(y,z)=2y_0z_0+y_1z_2+y_2z_1+y_3z_4+y_4z_3, \] a non-degenerate parabolic form with polar form $B$; the singular points form $Q(4,5)$. A point $\langle y\rangle$ is \emph{non-square} if $Q(y)\in\{2,3\}$ (this does not depend on the representative). The line $\ell=\langle e_1,e_3\rangle$ is totally singular; $\ell^\perp=\langle e_0,e_1,e_3\rangle$, and every point of $\ell^\perp\setminus\ell$ has $Q=t^2$ a non-zero square. So no non-square point lies in $\ell^\perp$, and for a non-square point $y$ the linear form $B(y,\cdot)$ is non-zero on $\ell$: it vanishes at exactly one point \[ P(y)=\langle y_4e_1-y_2e_3\rangle\in\ell . \] There are $300$ non-square points: of the $781$ points of $\mathrm{PG}(4,5)$, $156$ are singular and $325$ are square. \begin{construction}\label{con:306} The graph $\Delta$ has as vertices the $300$ non-square points and the $6$ points of $\ell$. The points of $\ell$ are pairwise adjacent; a non-square point $y$ is adjacent to the point $P(y)$ of $\ell$ and to no other point of $\ell$; two distinct non-square points $y,z$ are adjacent iff \[ \bigl(B(y,z)=0\ \text{ and }\ P(y)\neq P(z)\bigr)\qquad\text{or}\qquad z\in\langle y,P(y)\rangle . \] \end{construction} \begin{lemma}\label{lem:306local}\leavevmode \begin{enumerate} \item For a non-square $y$, the line $m_y=\langle y,P(y)\rangle$ consists of $P(y)$ and five non-square points, and $m_z=m_y$ for each of them. So the $300$ non-square points are partitioned into $60$ sets of size $5$, and each point of $\ell$ lies on $10$ of the lines $m_y$. \item The second alternative of Construction~\ref{con:306} implies $P(z)=P(y)$ and $B(y,z)\neq0$, so the two alternatives are disjoint and the relation is symmetric. \item $\ell$ and the $60$ sets $\{P(y)\}\cup(m_y\setminus P(y))$ are cliques of size $6=1-k/s$, i.e.\ Delsarte cliques. \end{enumerate} \end{lemma} \begin{proof} (1) $P=P(y)$ is singular and $B(y,P)=0$, so $Q(y+tP)=Q(y)$ for all $t$: the five points $\langle y+tP\rangle$ are non-square, and each has $P$ as its orthogonal point on $\ell$. A point of $\ell$ is $P(y)$ for $300/6=50$ points $y$ by the transitivity of the group $L$ below on $\ell$, i.e.\ for $10$ lines. (2) If $z=y+tP(y)$ ($t\ne0$, up to scalars), then $P(z)=P(y)$ and $B(y,z)=2Q(y)\neq0$. (3) The points of $m_y\setminus P$ are pairwise adjacent by the second alternative, and adjacent to $P$; $\ell$ is a clique by definition. $\Delta$ has $k=55$, $s=-11$. \end{proof} \begin{proposition}\label{prop:306aut} The stabiliser $L$ of $\ell$ in $\mathrm{SO}(5,5)$, of order $60000$, acts faithfully on $\Delta$ by automorphisms, transitively on the $300$ non-square points and on the $6$ points of $\ell$, inducing $\mathrm{PGL}(2,5)\cong S_5$ on $\ell$. \end{proposition} \begin{proof} $L$ preserves $Q$, $B$, $\ell$, the set of non-square points, and therefore the map $y\mapsto P(y)$ and the lines $m_y$; so it preserves every clause of the construction. $|\mathrm{SO}(5,5)|=5^4(5^2-1)(5^4-1)=9{,}360{,}000$ and $\mathrm{SO}(5,5)$ is transitive on the $156$ lines of $Q(4,5)$, so $|L|=60000$. For faithfulness, let $g\in L$ fix every non-square point. Fixing a spanning set of points is not enough by itself (a diagonal matrix fixes the basis points), so we use a projective frame: the five non-square vectors $(0,0,0,1,2)$, $(0,0,0,2,1)$, $(0,0,1,1,2)$, $(0,1,0,1,2)$, $(1,0,0,1,1)$ (all with $Q=2$) form a basis of $\F_5^5$, and the combination with coefficients $1,1,1,1,2$ is $(2,1,1,2,4)$, with $Q=3$, again non-square. Since $g$ fixes the six points, it multiplies each basis vector by a scalar, and since it fixes the point with all coefficients non-zero, these scalars are equal. (Alternatively: $g$ is diagonalisable, as the non-square points span $\F_5^5$ and are eigenvectors; if $g$ had two distinct eigenvalues, all $300$ non-square points would lie in the union of two complementary proper subspaces, which contains at most $156+1$ points.) So $g$ is a scalar, and the only scalar in $\mathrm{SO}(5,5)$ is $1$ (since $\det(-I)=-1$); so the action is faithful. $L$ induces $\mathrm{GL}(2,5)$ on the vector space $\ell$ (the Levi factor of the parabolic subgroup $L$), hence $\mathrm{PGL}(2,5)$ on the six points of $\ell$. Transitivity on the $300$ non-square points we checked by computer. \end{proof} \begin{computation}\label{comp:306} $\Delta$ is an $\srg(306,55,4,11)$ (exact check, Section~\ref{sec:verify}), $|\Aut\Delta|=60000$ (nauty), so $\Aut\Delta=L\cong5^{1+2}_+{:}\mathrm{GL}(2,5)$, with orbits $300+6$; $\Delta$ is not vertex-transitive. $\Delta$ has exactly $61$ cliques of size $6$, those of Lemma~\ref{lem:306local}(3), and $\omega(\Delta)=6$. $\Delta$ is isomorphic to the hit of Section~\ref{sec:hit306}. The induced subgraph on the $300$ non-square points is $54$-regular and every non-square point has exactly one neighbour on $\ell$; the partition $\{300,6\}$ is equitable with quotient eigenvalues $55$ and $4=r$. \end{computation} \emph{Relation to $\mathrm{NO}^{-\perp}_5(5)$} (computer; found by the referee and checked again). The graph on the $300$ non-square points in which two points are adjacent iff they are perpendicular is the known $\srg(300,65,10,15)$, denoted $\mathrm{NO}^{-\perp}_5(5)$ in \cite{BrouwerTable,BvM}. The restriction of $\Delta$ to the $300$ non-square points is this graph minus the perpendicular pairs with $P(y)=P(z)$ ($15$ per vertex) plus the pairs on a common line $m_y$ ($4$ per vertex): $65-15+4=54$. So $\Delta$ is obtained from $\mathrm{NO}^{-\perp}_5(5)$ by a modification inside the six classes $\{y:P(y)=p\}$, $p\in\ell$, of $50$ points each, together with the clique $\ell$ and the edges $\{y,P(y)\}$. A hand proof of strong regularity could go through the eigenspaces of $\mathrm{NO}^{-\perp}_5(5)$ and of this partition; we have not completed one. \begin{remark}[Not geometric]\label{rem:pseudoGQ} The parameters $(306,55,4,11)$ are those of the collinearity graph of a generalized quadrangle $\mathrm{GQ}(s,t)$ with $(s,t)=(5,10)$, i.e.\ $\srg((s+1)(st+1),s(t+1),s-1,t+1)$, so $\Delta$ is pseudo-geometric. No $\mathrm{GQ}(5,10)$ is known: $(5,10)$ is not of any of the forms $(1,q)$, $(q,1)$, $(q\pm1,q\mp1)$, $(q,q)$, $(q,q^2)$, $(q^2,q)$, $(q^2,q^3)$, $(q^3,q^2)$ of the known quadrangles \cite[\S6.3]{vDG}. The collinearity graph of a $\mathrm{GQ}(5,10)$ would contain its $(t+1)(st+1)=561$ lines as cliques of size $6$, whereas $\Delta$ has only $61$ cliques of size $6$ (Computation~\ref{comp:306}). So $\Delta$ is not geometric, and it says nothing about the existence of a $\mathrm{GQ}(5,10)$. Brouwer's row for $(306,55,4,11)$ has no comment. \end{remark} \begin{remark}[Other $q$] The same rule over $\F_q$ has $q^2(q^2-1)/2+q+1$ vertices, and its parameters, if it were strongly regular, would be those of a $\mathrm{GQ}(q,q(q-1)/2)$. We re-implemented Construction~\ref{con:306} from scratch over $\F_q$ for $q=3,5,7,9$ and checked it exactly. Over $\F_3$ it gives an $\srg(40,12,2,4)$ with $40$ cliques of size $4$, and nauty shows that it is isomorphic to the collinearity graph of the classical quadrangle $Q(4,3)$ (and not to that of its dual $W(3)$). Over $\F_5$ it gives $\Delta$ (same canonical form as our file). Over $\F_7$ it gives a $154$-regular graph on $1184$ vertices and over $\F_9$ a $333$-regular graph on $3250$ vertices, neither strongly regular; in both cases the perpendicularity graph on the non-square points is not strongly regular either. This matches what is known about these perpendicularity graphs on the nonisotropic points of one type of $Q(4,q)$: they are strongly regular for $q=3$ and for $q=5$ (Wilbrink; \cite[\S7.D]{BvL84}, \cite[\S3.1.4]{BvM}), and, by our exact checks, not for $q=7$ and $q=9$. (If the non-square points are replaced by the points with $Q$ a non-zero square, the map $P$ is undefined, because some of those points lie in $\ell^\perp$.) So the construction is a two-member pattern, $Q(4,3)$ for $q=3$ and $\Delta$ for $q=5$, and we claim $\Delta$ as a new graph on a new parameter set, not as a member of an infinite family. The construction also does not extend to quadrics in dimension $2m+1\ge7$ in an obvious way: it needs every chosen point to have a unique perpendicular point on the totally singular subspace $\ell$, which happens only when $\ell$ is a line of $Q(4,q)$. \end{remark} \section{Properties}\label{sec:props} \begin{table}[ht] \caption{Invariants of the graphs (computer results unless marked ``hand''). ``Del.'' is the number of Delsarte cliques. $H_2=\left(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\right)$. The first, third and fifth rows are the search hits up to isomorphism.}\label{tab:props} \centering\small \begin{tabular}{@{}llrlll@{}} \toprule graph & construction & $|\Aut|$ & orbits & VT & Del.\\ \midrule $\srg(306,55,4,11)$ & $\Delta$ & $60000$ & $300+6$ & no & $61$\\ $\srg(400,171,74,72)$ & $\Gamma(\mathrm{Pal}_{II}(9))$ & $5760$ & $360+40$ & no & $0$\\ $\srg(576,253,112,110)$ & $\Gamma(\mathrm{Pal}_{II}(5)\otimes H_2)$ & $760320$ & $576$ & yes & $0$\\ $\srg(784,351,158,156)$ & $\Gamma(\mathrm{Pal}_{II}(13))$ & $8736$ & $728+56$ & no & $0$\\ $\srg(1296,595,274,272)$ & $\Gamma(S-I)$, symplectic & $2903040$ & $1260+36$ & no & $64$\\ $\srg(1296,595,274,272)$ & $\Gamma(2E-J)$, $\Z_6$ & $3456$ & $864+288+144$ & no & $4$\\ $\srg(1296,595,274,272)$ & $\Gamma(2E-J)$, $S_3$ & $31104$ & $864+432$ & no & $12$\\ $\srg(1296,595,274,272)$ & $\Gamma(\mathrm{Pal}_{II}(17))$ & $19584$ & $1224+72$ & no & $0$\\ \bottomrule \end{tabular} \end{table} \emph{Automorphism groups of the hits} (nauty for the order and generators, GAP for the structure). \begin{itemize} \item $v=576$: $|\Aut|=760320=8|M_{12}|$; vertex-transitive but imprimitive, rank $13$, vertex stabiliser $L_2(11){:}2$. The derived subgroup has order $190080$ and two orbits of length $288$; $\Aut/\Aut'\cong C_2\times C_2$ and $|Z(\Aut)|=2$. $M_{12}$ has no subgroup of order $165$, hence no transitive action on $576$ points, so no transitive coset search over $M_{12}$ could see this graph. The reversal $(a,b)\mapsto(b,a)$ of Construction~\ref{con:gamma} and the automorphisms of the Hadamard matrix of order $12$ (unique up to equivalence, here $\mathrm{Pal}_{II}(5)$; its automorphism group is $2.M_{12}$) explain much of this group; we have not worked out the identification in detail. \item $v=306$: $\Aut\cong5^{1+2}_+{:}\mathrm{GL}(2,5)$ (Proposition~\ref{prop:306aut}); GAP's \code{StructureDescription} is $((C_5\times C_5){:}C_5){:}\mathrm{GL}(2,5)$. It acts on the $6$-clique as $S_5$. \item $v=1296$: $\Aut\cong\mathrm{Sp}(6,2)\times C_2$, the centre generated by the reversal; the derived group is the simple group $\mathrm{Sp}(6,2)$. Not vertex-transitive. \end{itemize} \emph{Delsarte cliques.} In $\Delta$ and in $\Gamma(S-I)$ the small orbit is a Delsarte clique on which the group acts $2$-transitively ($\mathrm{PGL}(2,5)$ on $6$ points, $\mathrm{Sp}(6,2)$ on $36$), and each vertex of the large orbit has the same number of neighbours in it ($1$ resp.\ $16$). In $\Delta$ the other $60$ Delsarte cliques partition the large orbit together with one point of $\ell$ each (Lemma~\ref{lem:306local}). In $\Gamma(S-I)$ there are $63$ further Delsarte cliques, of the form $\{(a,\pi a)\}$. \emph{Complements.} The complements are strongly regular with the parameters of Table~\ref{tab:params} and have the same automorphism groups. The complement of $\Gamma(H)$ has the parameters of $\mathrm{LS}_{n/2+2}(n)$ (eigenvalues $\frac n2-2$ and $-\frac n2-2$); its Delsarte cliques are the cocliques of size $n$ of $\Gamma(H)$, for instance the rows and the columns of $[n]\times[n]$. In the seven graphs $\Gamma(H)$ of Table~\ref{tab:props} the vertex $(0,0)$ lies in $40$ ($n=20$), $116$ ($n=24$), $56$ ($n=28$) and $72$ (each of the four graphs with $n=36$) cocliques of size $n$ (exhaustive enumeration, \code{props.py cocl\_count}). If the complement of $\Gamma(H)$ were the Latin square graph of an $\mathrm{OA}(n,\frac n2+2)$, then the $\frac n2+2$ lines through $(0,0)$ would be cocliques of size $n$ of $\Gamma(H)$ that partition the non-neighbours of $(0,0)$. The first version of this paper concluded ``not a Latin square graph'' from the observation that the cocliques through $(0,0)$ cover some non-neighbours more than once. That observation alone is not enough, since a Latin square graph may have Delsarte cliques besides its lines. We have therefore tested the condition itself: an exact-cover search over the cocliques of size $n$ through $(0,0)$ finds \emph{no} subfamily that partitions the non-neighbours of $(0,0)$, for each of the seven graphs (\code{cocl\_cover.py}; as a control it finds the partition in the complements of genuine Latin square graphs $\mathrm{LS}_3(5)$, $\mathrm{LS}_4(7)$, $\mathrm{LS}_5(11)$). So the complements are not Latin square graphs either, and they say nothing about $\mathrm{OA}(n,\frac n2+2)$. The coclique counts and the exact-cover result were checked by three programs. The program \code{cocl\_cover.py} reproduces all counts of \code{props.py}, but it re-implements the same branch-and-bound and is therefore not an independent check. The count $40$ for $n=20$ was reproduced by an independent program in the first referee review; for $n=24,28,36$ that program's plain backtracking was stopped at its 25-minute limit. The second referee review reproduced all seven counts, $40$, $116$, $56$ and $72$ (four times), with a program written from scratch that uses a different algorithm (\code{cocl.c}: bitset enumeration of the $n$-cocliques through a vertex, pruned by the fact that a coclique of size $n$ attains the Hoffman bound, so every vertex outside it has exactly $kn/(v-n)$ neighbours in it), re-checked every listed coclique, and found with its own exact-cover program (\code{v6\_cover.py}) no subfamily partitioning the non-neighbours of $(0,0)$ in any of the seven graphs; as controls it finds $3$, $5$ and $6$ cocliques and the partition in the complements of $\mathrm{LS}_3(7)$, $\mathrm{LS}_5(11)$ and $\mathrm{LS}_6(13)$ (Data availability). Only the statement about the complements depends on these counts; the statement that the graphs $\Gamma(H)$ themselves are not Latin square graphs (Computation~\ref{comp:perm}) does not. \section{Verification}\label{sec:verify} \subsection{The standalone verifier} Appendix~\ref{app:verify} lists \code{verify\_srg.py}, a program of about $60$ lines that uses only the Python standard library. It decodes graph6 itself (no graph library), rejects malformed input, checks that the graph is loopless and $k$-regular, and computes the number of common neighbours of every pair of vertices with integer bitsets. The graph is accepted iff these numbers take one value $\lambda$ on edges and one value $\mu$ on non-edges; with regularity this is exactly $A^2=kI+\lambda A+\mu(J-I-A)$. The graphs were written by \code{build\_all.py} (Appendix~\ref{app:build}), also standard-library Python, directly from Constructions~\ref{con:gamma} and~\ref{con:306}; the three hits of the search are archived unchanged as \code{hit*.g6}. The complete run log: {\scriptsize \begin{verbatim} # 2026-10-10T20:49Z Python 3.12.3 verify_srg.py sha256 26954cc37ba0bc89 srg306_55_4_11.g6:1 n=306 OK srg(306,55,4,11); complement srg(306,250,205,200) srg400_171_74_72.g6:1 n=400 OK srg(400,171,74,72); complement srg(400,228,128,132) srg576_253_112_110.g6:1 n=576 OK srg(576,253,112,110); complement srg(576,322,178,182) srg784_351_158_156.g6:1 n=784 OK srg(784,351,158,156); complement srg(784,432,236,240) srg1296_595_274_272.g6:1 n=1296 OK srg(1296,595,274,272); complement srg(1296,700,376,380) srg1296_595_274_272_latin.g6:1 n=1296 OK srg(1296,595,274,272); complement srg(1296,700,376,380) srg1296_595_274_272_latinS3.g6:1 n=1296 OK srg(1296,595,274,272); complement srg(1296,700,376,380) srg1296_595_274_272_paley.g6:1 n=1296 OK srg(1296,595,274,272); complement srg(1296,700,376,380) hit306_55_4_11.g6:1 n=306 OK srg(306,55,4,11); complement srg(306,250,205,200) hit576_253_112_110.g6:1 n=576 OK srg(576,253,112,110); complement srg(576,322,178,182) hit1296_595_274_272.g6:1 n=1296 OK srg(1296,595,274,272); complement srg(1296,700,376,380) # elapsed 30.52 s \end{verbatim}} \subsection{Isomorphisms and invariants} \code{canon.py} runs \code{dreadnaut} \cite{nauty} on each file and hashes the complete canonical graph (SHA-256 of the canonically labelled adjacency lists, not nauty's short invariant hash). The hits and the constructed graphs agree: \begin{center}\small \begin{tabular}{@{}llll@{}} \toprule hit & construction & $|\Aut|$ & canonical-graph hash (first 24 hex digits)\\ \midrule \code{hit306\_55\_4\_11} & $\Delta$ & $60000$ & \code{0acaba04381acca2cfcd860f}\\ \code{hit576\_253\_112\_110} & $\Gamma(\mathrm{Pal}_{II}(5)\otimes H_2)$ & $760320$ & \code{98c94ff1a884a7bc0010376c}\\ \code{hit1296\_595\_274\_272} & $\Gamma(S-I)$, symplectic & $2903040$ & \code{f6e4778ab9f38293287f5d7a}\\ \bottomrule \end{tabular} \end{center} The other four graphs on $1296$, $400$ and $784$ vertices have pairwise different hashes and automorphism group orders (Table~\ref{tab:props}). \subsection{How the claims were checked} Each hit was established several times, by separate programs and in separate AI sessions (Acknowledgements): \begin{enumerate} \item found by the CP-SAT model and checked by exact integer $A^2$ on the full matrix (\code{solve.py}); \item rebuilt from scratch in GAP without TomLib representatives and without the CP-SAT model, by exhaustive search over all unions of orbitals and over all conjugacy classes of the relevant subgroups (Section~\ref{sec:hits}); \item checked by two earlier independent checkers (\code{verify\_g6.py}, own graph6 decoder and set intersections; \code{verify\_hit\_full.py}, exact $A^2$ in NumPy integers, spectrum and connectivity), in a separate coordinating session; \item rebuilt from the explicit constructions of this paper, which were found afterwards and are not tied to the search code, and checked by \code{verify\_srg.py}; \item for the graphs $\Gamma(H)$, proved strongly regular by hand (Theorems~\ref{thm:bush} and~\ref{thm:hadamard}); the construction also predicts the spectrum, which agrees with the spectra computed in (3); \item re-checked in two referee reviews by a different model family, each with its own code written from scratch (own graph6 decoder and exact integer $A^2$ for all eleven files, own rebuilds of every construction, nauty canonical forms, $|\Aut|$ and orbits, clique counts; in the second review also the Kharaghani graphs, the coclique counts and exact cover of Section~\ref{sec:props}, and an own SAT model for $n=12$); they reproduced every computational claim they checked; the claims not re-checked include the search pipeline and the GAP computations of Sections~\ref{sec:method}, \ref{sec:hits} and~\ref{sec:props} and the $q=9$ analogue of $\Delta$ (the $n=20$ SAT timeouts support nothing); \item for the comparison with Kharaghani's matrices (Sections~\ref{sec:khar}, \ref{sec:noniso}, \ref{sec:third}) and the $q$-analogues of $\Delta$, a further program written from scratch that rebuilds the graphs of this paper with the same canonical forms. \end{enumerate} For $\Delta$ there is no hand proof of strong regularity yet; its status rests on (1)--(4) and (6). \section{Novelty}\label{sec:novelty} We claim that the five parameter sets are new as far as we can determine, and we list here exactly what we checked. \emph{Brouwer's table.} On 10 October 2026 we read the live pages of \cite{BrouwerTable}, and we re-read them on 11 October 2026 (04:02 UTC). The rows were: \code{? 306 55 4 11} (page $301$--$350$, no comment); \code{? 400 171 74 72} (page $351$--$400$, comment ``OA(20,9)?'', complement ``OA(20,12)?''); \code{? 576 253 112 110} (page $551$--$600$, comment ``OA(24,11)?'', complement ``OA(24,14)?''); \code{? 784 351 158 156} (page $751$--$800$, comment ``OA(28,13)?'', complement ``OA(28,16)?''); \code{? 1296 595 274 272} (page $1251$--$1300$, comment ``OA(36,17)?'', complement ``OA(36,20)?''). The comments refer to the Latin square graphs that orthogonal arrays $\mathrm{OA}(n,\frac n2-1)$, i.e.\ $\frac n2-3$ mutually orthogonal Latin squares of order $n$, would give. No such array is known for $n=20,24,28,36$: it would need $7$, $9$, $11$ resp.\ $15$ mutually orthogonal Latin squares, while the best known lower bounds are $N(20)\ge4$, $N(24)\ge7$, $N(28)\ge5$ and $N(36)\ge8$ \cite[Table~III.3.87]{HCD}. Our graphs are not Latin square graphs (Computation~\ref{comp:perm}), so they leave these questions open. The neighbouring rows show what is known. For $n=20$ they read \begin{center}\small \code{+ 400 190 90 90 \ \ OA(20,10)?; Wallis (AR(2,5)+S(2,2,20)); RSHCD+; 2-graph}\\ \code{+ 400 209 108 110 \ OA(20,11)?; Wallis2 (AR(2,5)+S(2,2,20)); Goethals-Seidel(2,19); 2-graph} \end{center} and the rows $(576,276,132,132)$, $(576,299,154,156)$, $(784,378,182,182)$, $(784,405,208,210)$, $(1296,630,306,306)$ and $(1296,665,340,342)$ are analogous. These are the parameters of $\mathrm{LS}_{n/2}(n)$ (one spread deleted, Theorem~\ref{thm:bush}(3)) and of $\mathrm{LS}_{n/2+1}(n)$ (the graph $\Gamma_0$). The rows of $\mathrm{LS}_{n/2-1}(n)$ type carry only the comment ``$\mathrm{OA}(n,n/2-1)$?'', so the table records no construction that deletes a second spread. The rows of $\mathrm{LS}_{n/2-2}(n)$ type, which a third spread would give (Section~\ref{sec:third}), are also ``?''. \emph{Bush-type Hadamard matrices.} We read Bonato, Holzmann and Kharaghani \cite{BHK01} in full. Their Theorem~1 is Kharaghani's construction \cite{Kh85} (Proposition~\ref{prop:khar}); we could not obtain \cite{Kh85} itself and know it through this reproduction. Their Lemma~3 deletes the diagonal blocks, i.e.\ one spread, and gives the twin graphs $\srg(4m^2,2m^2-m,m^2-m,m^2-m)$; their Theorem~5 and Conjecture~8 concern the $3$-e.c.\ property of these twin graphs. The paper does not delete a second spread. We also looked at the work on Bush-type matrices of order $4m^2$ with $m$ odd \cite{JKT01,MX06}, which is about a different question (existence of the matrices), and at the Wallis--Fon-Der-Flaass constructions and their generalisations \cite{Wallis71,FDF02,Muz07,Kab21}. On these vertex numbers they give the ``$+$'' rows quoted above (``Wallis'', ``Wallis2''); none of them deletes two spreads, and none of the strongly regular families stated in \cite{Kab21} has $\lambda=\mu+2$ (this last check was made in the referee review). Haemers and Tonchev \cite{HT96} study spreads and give the $3$-class scheme behind Lemma~\ref{lem:spread}, but do not apply it to Bush-type matrices. \emph{Coset-graph constructions.} The Rijeka group has constructed many strongly regular graphs from transitive actions of finite groups, e.g.\ from the Mathieu groups \cite{CMS21} (whose $M_{12}$ graphs are $\srg(66,20,10,4)$, $(144,66,30,30)$, $(144,55,22,20)$, $(144,22,10,2)$, $(495,238,109,119)$) and from $\mathrm O^\pm(6,2)$ \cite{CRS18} (transitive actions on at most $600$ vertices). Their methods are restricted to vertex-transitive graphs; four of our graphs are not vertex-transitive, and the vertex-transitive graph on $576$ vertices admits no transitive action of $M_{12}$ (Section~\ref{sec:props}). \emph{Other literature.} We also looked at the classical sources \cite{GS70,Seidel76} and at the book \cite{BvM}, but we did not read the full text of \cite{GS70} or search the full text of \cite{BvM} for remarks on deleting spreads from graphs of Latin square type. For the graph on $306$ vertices we checked the list of known generalized quadrangles in \cite[\S6.3]{vDG} (Remark~\ref{rem:pseudoGQ}); we found no source for $\srg(306,55,4,11)$ or for a pseudo-geometric graph with the parameters of a $\mathrm{GQ}(5,10)$. \emph{Web searches} (10 and 11 October 2026) for the five parameter tuples with and without the prefix ``srg'', for their complements, for ``$M_{12}$'' and ``$L_2(11)$'' with $576$ vertices, ``$\mathrm{Sp}(6,2)$'' with $1296$, and for strongly regular graphs from symmetric or Bush-type Hadamard matrices on $n^2$ vertices found no construction of a graph with any of these parameter sets. MathSciNet was not searched, and a construction inside a paper on another subject could have been missed. \emph{Claim.} As far as we can determine, the five parameter sets had no known construction, and the graphs are new. For the four sets of $\mathrm{LS}_{n/2-1}(n)$ type the construction is a short step from \cite{Kh85,BHK01}: the new ingredient is the second, orthogonal spread. Whether the general statement of Corollary~\ref{cor:every} has been observed before in a form we did not find, we cannot exclude; the rows of \cite{BrouwerTable} indicate that it has not been applied to these parameter sets. \section{The pattern: a Delsarte clique plus one orbit}\label{sec:pattern} In $\Delta$ and in the hit on $1296$ vertices the group has two orbits, the small one is a Delsarte clique, and the group is $2$-transitive on it: $\mathrm{PGL}(2,5)$ on $\mathrm{PG}(1,5)$ and $\mathrm{Sp}(6,2)$ on its $36$ forms of plus type. For $\Gamma(S-I)$ this shape is explained by Proposition~\ref{prop:twograph}: the diagonal is always a Delsarte clique, and when $\Aut(\mathcal T)$ is $2$-transitive on points the off-diagonal pairs form one orbit. For $\Delta$ we have no such explanation. Let $\omega=1-k/s$; if a Delsarte clique $C$ is an orbit, then $c=\omega(k-\omega+1)/(v-\omega)$ must be an integer (it is the number of neighbours in $C$ of an outside vertex), and $\{C,V\setminus C\}$ is an equitable partition whose quotient has eigenvalue $\omega-1-c=r$. \begin{question} For which open parameter sets with integral eigenvalues is there a group $G$ with a $2$-transitive action of degree $\omega=1-k/s$ and a second orbit of length $v-\omega$ that carries an $\srg(v,k,\lambda,\mu)$ in which the first orbit is a Delsarte clique? Is there a construction that contains both $\Delta$ and the collinearity graph of $Q(4,3)$ (its $q=3$ analogue) and continues beyond $q=5$? \end{question} A search of this kind need not be restricted to TomLib: it only needs the $2$-transitive group and the transitive permutation groups of degree $v-\omega$ containing it as a quotient, or the groups of rank at most a few on the second orbit. We have not run it. We also have not checked why the two-orbit search did not find $\Gamma(\mathrm{Pal}_{II}(9))$ and $\Gamma(\mathrm{Pal}_{II}(13))$, whose automorphism groups have two orbits; their groups may not be in TomLib, or may lie beyond the rank limits of Section~\ref{sec:method}. \section{Status of the claims}\label{sec:status} \begin{table}[ht] \caption{How each claim is established.}\label{tab:status} \centering\small \begin{tabular}{@{}p{0.52\textwidth}p{0.42\textwidth}@{}} \toprule Claim & Established by\\ \midrule Lemma~\ref{lem:spread} (spread deletion) & hand (essentially \cite[Prop.~4.1]{HT96})\\ Theorem~\ref{thm:bush}, Proposition~\ref{prop:khar}, Lemma~\ref{lem:symbush}, Corollary~\ref{cor:every} & hand (Proposition~\ref{prop:khar} is due to \cite{Kh85})\\ Theorem~\ref{thm:hadamard} ($\Gamma(H)$ strongly regular, spectrum) & hand, two proofs\\ graphs of Computation~\ref{comp:khar}, including $v=1600$, $1936$ & computer: exact check\\ $\mathrm{Pal}_{II}(q)$ symmetric Hadamard; Corollary~\ref{cor:exist} & classical \cite{Paley,CK07}; also checked by computer\\ Proposition~\ref{prop:twograph}, Lemma~\ref{lem:perm}, Lemma~\ref{lem:306local} & hand\\ $\Delta$ is $\srg(306,55,4,11)$ & computer: exact check (several programs)\\ $L\le\Aut\Delta$, faithful, $\mathrm{PGL}(2,5)$ on $\ell$ & hand\\ $|\Aut|$ of all graphs, orbits, structure of $\Aut$ & computer (nauty; GAP)\\ non-isomorphism (Computations~\ref{comp:1296}, \ref{comp:noniso}) & computer (nauty canonical forms)\\ counts of $n$-cliques; not Latin square graphs & computer (exhaustive; three independent programs)\\ counts of $n$-cocliques through $(0,0)$; complements not Latin square graphs (exact cover) & computer; three independent programs for $n=20$; for $n=24,28,36$ three programs, two of them independent (Section~\ref{sec:props})\\ no third spread in the tested graphs; SAT results of Computation~\ref{comp:third}; for $\mathrm{Pal}_I(11)$, hence every Kharaghani matrix of order $144$: no third spread & computer (exhaustive search; SAT solver, two independent models for $n=12$); symmetry breaking and reduction to $\mathrm{Pal}_I(11)$ by hand; $n=20$ SAT runs without verdict\\ the hits are isomorphic to $\Delta$, $\Gamma(\mathrm{Pal}_{II}(5)\otimes H_2)$, $\Gamma(S-I)$ & computer (canonical forms)\\ coset descriptions of the hits; uniqueness on the stated actions & computer (CP-SAT and exhaustive GAP rebuild)\\ Table~\ref{tab:1296orb} labels & computer\\ description of $\Delta$ via $\mathrm{NO}^{-\perp}_5(5)$; $61$ six-cliques, not geometric & computer (two programs)\\ $q=3,7,9$ analogues of $\Delta$; $q=3$ gives $Q(4,3)$ & computer (exact check; canonical forms)\\ status in \cite{BrouwerTable} on 10 and 11 October 2026 & reading the live pages\\ \bottomrule \end{tabular} \end{table} \section*{Data availability} {\raggedright The programs of this paper are in \code{scripts/\brk new\_srgs\_multiorbit/}: \code{build\_all.py} (all constructions; Appendix~\ref{app:build}), \code{verify\_srg.py} (Appendix~\ref{app:verify}), \code{canon.py}, \code{props.py} (clique, coclique and $q=3,7$ computations), \code{hadamard\_graph.py}, \code{twograph1296.py}, \code{twograph\_family.py}, \code{check\_stabilisers.g} (the stabiliser $S_4\wr S_2$), and the exploration scripts \code{explore306.py}, \code{explore1296.py}, \code{explore576.g}. The search programs are in \code{scripts/\brk find2026\_10\_11/} (\code{stage1.g}, \code{filter2.py}, \code{export.g}, \code{solve.py}, \code{driver.py}, \code{rebuild\_576.g}, \code{rebuild\_two\_orbit.g}, \code{verify\_g6.py}); the run directory with all job lists and result files is available from the author. The programs for Sections~\ref{sec:khar}, \ref{sec:noniso}, \ref{sec:third} and the $q$-analogues of $\Delta$ are in \code{scripts/\brk family\_2026\_10\_12/} (\code{famlib.py}, \code{step2\_known.py}, \code{step2\_c.py}, \code{step3\_spreads.py}, \code{step3\_files.py}, \code{transv.c}, \code{sat\_third\_spread.py}, \code{step4\_delta.py}, \code{cocl\_cover.py} with its controls \code{cocl\_cover\_controls.py}, \code{wlog\_check.py}), with logs and graphs in \code{out/\brk family\_2026\_10\_12/}; the programs and logs of the first referee review are in \code{out/\brk referee\_multiorbit\_fable/}, those of the second (among them \code{cocl.c}, \code{v6\_cover.py}, \code{v6\_controls.py}, \code{v8\_sat12.py}) in \code{out/\brk referee\_multiorbit\_v2\_fable/}. The graphs are in \code{out/\brk new\_srgs\_multiorbit/}, one graph6 line (ending in LF) per file, in the vertex order of \code{build\_all.py}: for $\Gamma(H)$ the vertex $(a,b)$ has index $an+b$; for $\Delta$ the $300$ non-square points come first, then the $6$ points of $\ell$, each in lexicographic order of normalised coordinates (first non-zero coordinate $1$). The files \code{hit*.g6} are the search hits in the vertex order of the search. SHA-256 checksums:\par} \begin{center}\scriptsize \begin{tabular}{@{}ll@{}} \code{srg306\_55\_4\_11.g6} & \code{68139471b37b8747c0387b6564949da70243b689eaff7b0c40394fe0621666f4}\\ \code{srg400\_171\_74\_72.g6} & \code{a5abf2e29679204253603b29b026a75f004342e6a2a29afef1affaa884b5f95f}\\ \code{srg576\_253\_112\_110.g6} & \code{de1d020f27e8a608bc138adbb4ad0770c0b49d8f45088e7cc444cf34a6d2cf8f}\\ \code{srg784\_351\_158\_156.g6} & \code{0483e16d5bf9f656c26a923755c10d334ec25f6693aea2b7ccfb8303bd9bb0ac}\\ \code{srg1296\_595\_274\_272.g6} & \code{ea647de0a9ac4ea7d0b27b5b55fc9ecd4e90eccd3d51ff1d4c1a2ccc39f884c2}\\ \code{srg1296\_595\_274\_272\_latin.g6} & \code{02da950da5d20471bca39007c6084d23d80630a6f64c87eccd1ae990eb0d4ffc}\\ \code{srg1296\_595\_274\_272\_latinS3.g6} & \code{57e8730ff425f6b23b12e9d62c7d373ca9d5b204429f8c36d3dd5230d9055dc2}\\ \code{srg1296\_595\_274\_272\_paley.g6} & \code{040e34f430c48a95cb4bf804ac5fcbd294664875e6b92a8a0291792958ff7bcb}\\ \code{hit306\_55\_4\_11.g6} & \code{6e8abae2680e2ca9f36a06c85e29191c7b46f336f87bb47637f8a8e2a0136f03}\\ \code{hit576\_253\_112\_110.g6} & \code{06d3394fc8b72e806809b9ccc3d73664cfd517091b6b05a1fc4633da5b86b016}\\ \code{hit1296\_595\_274\_272.g6} & \code{e580257894cf2c86e9be23dc22c6b73792c598ead271ac4fd398acc71fbca61e}\\ \end{tabular} \end{center} \section*{Acknowledgements} \emph{Use of AI systems.} This work was done with substantial assistance from AI systems. They are not authors; the author is responsible for all content and is the mathematical expert who must accept every claim. Claude (Anthropic) designed and ran the two-orbit search with its controls and rebuilt the hits (one session); a separate session, coordinating the project, re-verified the hits with independent checkers; a third session found the explicit constructions, the symmetric Hadamard matrix construction and its proof, wrote the builders, the standalone verifier and the remaining computations, did the literature check, and drafted the first version of this paper. These sessions used the same model family, so their agreement is evidence of correct computation but not an independent mathematical review. The first version was then reviewed by a referee session of a different model family (Claude Fable), which re-derived the proofs, re-implemented every computation from scratch, and pointed out the closest prior work \cite{Kh85,BHK01}, the generalization to all Hadamard orders and the gaps corrected in this version. A further session compared the graphs with the known constructions and wrote the computations of Sections~\ref{sec:khar}, \ref{sec:noniso} and~\ref{sec:third}; the exact-cover test of Section~\ref{sec:props} was added in the second version. The second version was reviewed in a second referee round by a session of the same model family as the first referee (Claude Fable), again with its own code; it reproduced the coclique counts and the exact-cover result independently, gave its own SAT model for $n=12$, confirmed the symmetry-breaking argument of Computation~\ref{comp:third}, and asked for the citation and notation corrections made in this version. Every statement is established as recorded in Table~\ref{tab:status}. \begin{thebibliography}{99} \bibitem{BrouwerTable} A.~E. Brouwer, \emph{Parameters of strongly regular graphs}, online tables, \url{https://aeb.win.tue.nl/graphs/srg/srgtab.html} (pages for $301\le v\le400$, $551\le v\le600$, $751\le v\le800$ and $1251\le v\le1300$ accessed 10 October 2026, re-read 11 October 2026). \bibitem{BHK01} A.~Bonato, W.~H. Holzmann and H.~Kharaghani, Hadamard matrices and strongly regular graphs with the 3-e.c. adjacency property, \emph{Electron. J. Combin.} \textbf{8} (2001), \#R1. \bibitem{BvL84} A.~E. Brouwer and J.~H. van Lint, Strongly regular graphs and partial geometries, in \emph{Enumeration and Design}, Academic Press, 1984, 85--122. \bibitem{Bush71} K.~A. Bush, Unbalanced Hadamard matrices and finite projective planes of even order, \emph{J. Combin. Theory Ser.~A} \textbf{11} (1971), 38--44. \bibitem{BvM} A.~E. Brouwer and H.~Van Maldeghem, \emph{Strongly Regular Graphs}, Encyclopedia of Mathematics and its Applications 182, Cambridge University Press, 2022, doi:10.1017/9781009057226. \bibitem{CK07} R.~Craigen and H.~Kharaghani, Hadamard matrices and Hadamard designs, in C.~J. Colbourn and J.~H. Dinitz (eds.), \emph{Handbook of Combinatorial Designs}, 2nd ed., Chapman \& Hall/CRC, 2007, 273--280. \bibitem{CMS21} D.~Crnkovi\'c, N.~Mostarac and A.~\v{S}vob, Distance-regular graphs obtained from the Mathieu groups, arXiv:2101.02790, 2021. \bibitem{CRS18} D.~Crnkovi\'c, S.~Rukavina and A.~\v{S}vob, New strongly regular graphs from orthogonal groups $O^+(6,2)$ and $O^-(6,2)$, \emph{Discrete Math.} \textbf{341} (2018), 2723--2728, doi:10.1016/j.disc.2018.06.029. \bibitem{FDF02} D.~G. Fon-Der-Flaass, New prolific constructions of strongly regular graphs, \emph{Adv. Geom.} \textbf{2} (2002), 301--306. \bibitem{GAP} The GAP~Group, \emph{GAP -- Groups, Algorithms, and Programming}, Version 4.12.1, 2022, \url{https://www.gap-system.org}. \bibitem{GS70} J.-M. Goethals and J.~J. Seidel, Strongly regular graphs derived from combinatorial designs, \emph{Canad. J. Math.} \textbf{22} (1970), 597--614. \bibitem{HCD} C.~J. Colbourn and J.~H. Dinitz (eds.), \emph{Handbook of Combinatorial Designs}, 2nd ed., Chapman \& Hall/CRC, Boca Raton, 2007. \bibitem{HT96} W.~H. Haemers and V.~D. Tonchev, Spreads in strongly regular graphs, \emph{Des. Codes Cryptogr.} \textbf{8} (1996), 145--157. \bibitem{JKT01} Z.~Janko, H.~Kharaghani and V.~D. Tonchev, The existence of a Bush-type Hadamard matrix of order $324$ and two new infinite classes of symmetric designs, \emph{Des. Codes Cryptogr.} \textbf{24} (2001), 225--232. \bibitem{Kab21} V.~V. Kabanov, New versions of the Wallis--Fon-Der-Flaass construction to create divisible design graphs, arXiv:2111.10799, 2021. \bibitem{Kh85} H.~Kharaghani, New classes of weighing matrices, \emph{Ars Combin.} \textbf{19} (1985), 69--72. \bibitem{KovalZ} A.~Kova\v{l}, New strongly regular graphs on open parameter sets of Brouwer's table, preprint, Zenodo, 2026, doi:10.5281/zenodo.23210829. \bibitem{KovalTG} A.~Kova\v{l}, The regular two-graphs on $126$ and $176$ points are unique, preprint, Zenodo, 2026, doi:10.5281/zenodo.23279444. \bibitem{McKS01} B.~D. McKay and E.~Spence, Classification of regular two-graphs on $36$ and $38$ vertices, \emph{Australas. J. Combin.} \textbf{24} (2001), 293--300. \bibitem{MX06} M.~Muzychuk and Q.~Xiang, Symmetric Bush-type Hadamard matrices of order $4m^4$ exist for all odd $m$, \emph{Proc. Amer. Math. Soc.} \textbf{134} (2006), 2197--2204. \bibitem{Muz07} M.~Muzychuk, A generalization of Wallis--Fon-Der-Flaass construction of strongly regular graphs, \emph{J. Algebraic Combin.} \textbf{25} (2007), 169--187. \bibitem{nauty} B.~D. McKay and A.~Piperno, Practical graph isomorphism, II, \emph{J. Symbolic Comput.} \textbf{60} (2014), 94--112; \code{dreadnaut} of nauty 2.8.8. \bibitem{ORTools} L.~Perron and F.~Didier, \emph{CP-SAT}, OR-Tools, Google, \url{https://developers.google.com/optimization}. \bibitem{Paley} R.~E.~A.~C. Paley, On orthogonal matrices, \emph{J. Math. Phys.} \textbf{12} (1933), 311--320. \bibitem{Seidel76} J.~J. Seidel, A survey of two-graphs, in \emph{Colloquio Internazionale sulle Teorie Combinatorie} (Roma, 1973), Tomo I, Accad. Naz. Lincei, Rome, 1976, 481--511. \bibitem{TomLib} T.~Merkwitz, L.~Naughton and G.~Pfeiffer, \emph{TomLib, the GAP library of tables of marks}, Version 1.2.11, GAP package. \bibitem{vDG} E.~R. van Dam and K.~Guo, Pseudo-geometric strongly regular graphs with a regular point, arXiv:2204.04755v3, 2026. \bibitem{Wallis71} W.~D. Wallis, Construction of strongly regular graphs using affine designs, \emph{Bull. Austral. Math. Soc.} \textbf{4} (1971), 41--49; corrigendum, \emph{Bull. Austral. Math. Soc.} \textbf{5} (1971), 431. \end{thebibliography} \appendix \section{The standalone verifier}\label{app:verify} \begin{lstlisting} #!/usr/bin/env python3 """Standalone exact verifier (Python 3 standard library only). For every graph6 line in the given files: decode it, check that the graph is simple and k-regular, and check A^2 = k I + lambda A + mu (J - I - A) entry by entry in exact integers (common-neighbour counts of all pairs, computed with Python integers as bitsets). Prints the parameters and OK, or the first failure. Usage: verify_srg.py FILE.g6 [...] """ import sys def decode(line): b = [ord(c) - 63 for c in line.strip()] if any(x < 0 or x > 63 for x in b): raise ValueError('not graph6') if b[0] < 63: n, pos = b[0], 1 elif b[1] < 63: n, pos = (b[1] << 12) | (b[2] << 6) | b[3], 4 else: raise ValueError('n too large') need = n * (n - 1) // 2 if len(b) - pos != (need + 5) // 6: raise ValueError('wrong length') rows = [0] * n q = 0 for j in range(1, n): for i in range(j): if (b[pos + q // 6] >> (5 - q % 6)) & 1: rows[i] |= 1 << j; rows[j] |= 1 << i q += 1 return n, rows def check(n, rows): if any(rows[x] >> x & 1 for x in range(n)): return 'FAIL loop' deg = {bin(r).count('1') for r in rows} if len(deg) != 1: return 'FAIL not regular: degrees %s' % sorted(deg) k = deg.pop() if not 0 < k < n - 1: return 'FAIL complete or empty' lam = mu = None for x in range(n): rx = rows[x] for y in range(x + 1, n): c = bin(rx & rows[y]).count('1') if rx >> y & 1: if lam is None: lam = c elif c != lam: return 'FAIL adjacent pair (%d,%d): %d common neighbours, expected %d' % (x, y, c, lam) else: if mu is None: mu = c elif c != mu: return 'FAIL non-adjacent pair (%d,%d): %d common neighbours, expected %d' % (x, y, c, mu) if mu is None: return 'FAIL no non-adjacent pair' # A^2 = kI + lam A + mu(J-I-A): diagonal entries are the degrees (= k), off-diagonal entries checked above. return 'OK srg(%d,%d,%d,%d); complement srg(%d,%d,%d,%d)' % (n, k, lam, mu, n, n - k - 1, n - 2 - 2 * k + mu, n - 2 * k + lam) if __name__ == '__main__': bad = 0 for fn in sys.argv[1:]: with open(fn) as fh: for ln, line in enumerate(fh, 1): if not line.strip(): continue n, rows = decode(line) res = check(n, rows) bad += not res.startswith('OK') print('%s:%d n=%d %s' % (fn, ln, n, res), flush=True) sys.exit(1 if bad else 0) \end{lstlisting} \section{The builders}\label{app:build} \begin{lstlisting} #!/usr/bin/env python3 """Builders for the graphs of docs/paper/new_srgs_multiorbit.tex (standard library only). Gamma(H) for a symmetric Hadamard matrix H of order n: vertices (a,b) in [n]x[n]; (a,b) ~ (c,d) iff a != c, b != d, H[a][b]H[b][c]H[c][d]H[d][a] = 1. Delta_306 the graph on the 300 non-square points of Q(4,5) and the 6 points of a totally singular line l. Writes out/new_srgs_multiorbit/.g6 (one graph per file, one line + LF). Usage: build_all.py [OUTDIR] [names...] (default: all)""" import itertools, os, sys # ---------------------------------------------------------------- graph6 def to_g6(n, adj): """adj: list of sets. graph6 for n < 258048.""" if n < 63: head = [n] else: head = [63, (n >> 12) & 63, (n >> 6) & 63, n & 63] bits = [] for j in range(1, n): for i in range(j): bits.append(1 if j in adj[i] else 0) while len(bits) % 6: bits.append(0) body = [sum(bits[t + s] << (5 - s) for s in range(6)) for t in range(0, len(bits), 6)] return ''.join(chr(x + 63) for x in head + body) # ---------------------------------------------------------------- symmetric Hadamard matrices def kron(A, B): return [[A[i][j] * B[k][l] for j in range(len(A)) for l in range(len(B))] for i in range(len(A)) for k in range(len(B))] def jacobsthal(q): """Jacobsthal matrix of F_q, q = p or p^2 (F_{p^2} = F_p[i], i^2 = 2, 2 a non-square mod p for p = 3, 5).""" if q in (9, 25): p = 3 if q == 9 else 5 el = [(a, b) for a in range(p) for b in range(p)] mul = lambda x, y: ((x[0] * y[0] + 2 * x[1] * y[1]) % p, (x[0] * y[1] + x[1] * y[0]) % p) sq = {mul(x, x) for x in el if x != (0, 0)} sub = lambda x, y: ((x[0] - y[0]) % p, (x[1] - y[1]) % p) chi = lambda x: 0 if x == (0, 0) else (1 if x in sq else -1) return [[chi(sub(x, y)) for y in el] for x in el] sq = {(x * x) % q for x in range(1, q)} return [[0 if x == y else (1 if (x - y) % q in sq else -1) for y in range(q)] for x in range(q)] def paley2(q): """Paley II symmetric Hadamard matrix of order 2(q+1), q = 1 mod 4: H = C (x) [[1,1],[1,-1]] + I (x) [[1,-1],[-1,-1]], C the symmetric conference matrix [[0, 1^T], [1, Q]].""" Q = jacobsthal(q); m = q + 1 C = [[0] + [1] * q] + [[1] + Q[i] for i in range(q)] return [[(C[i][j] * [[1, 1], [1, -1]][s][t]) if i != j else [[1, -1], [-1, -1]][s][t] for j in range(m) for t in range(2)] for i in range(m) for s in range(2)] def symplectic36(): """H = S - I, S the Seidel matrix (-1)^{B(w_a,w_b)} on the 36 vectors w of F_2^6 with f0(w) = 0.""" B = lambda x, y: (x[0]*y[1] + x[1]*y[0] + x[2]*y[3] + x[3]*y[2] + x[4]*y[5] + x[5]*y[4]) % 2 f0 = lambda x: (x[0]*x[1] + x[2]*x[3] + x[4]*x[5]) % 2 W = [w for w in itertools.product((0, 1), repeat=6) if f0(w) == 0] return [[-1 if a == b else (-1) ** B(W[a], W[b]) for b in range(36)] for a in range(36)] def latin36(): """H = 2E - J, E the Latin square graph LS_3(6) of the cyclic Latin square of order 6 (an srg(36,15,6,6)).""" cells = [(i, j) for i in range(6) for j in range(6)] E = lambda x, y: x != y and (x[0] == y[0] or x[1] == y[1] or (x[0] + x[1] - y[0] - y[1]) % 6 == 0) return [[(1 if E(x, y) else -1) if x != y else -1 for y in cells] for x in cells] def latinS3(): """H = 2E - J, E the Latin square graph LS_3(6) of the Cayley table of S_3.""" G = list(itertools.permutations(range(3))) mul = lambda g, h: tuple(g[h[i]] for i in range(3)) L = [[G.index(mul(g, h)) for h in G] for g in G] cells = [(i, j) for i in range(6) for j in range(6)] E = lambda x, y: x != y and (x[0] == y[0] or x[1] == y[1] or L[x[0]][x[1]] == L[y[0]][y[1]]) return [[(1 if E(x, y) else -1) if x != y else -1 for y in cells] for x in cells] def check_hadamard(H): n = len(H) assert all(H[i][j] == H[j][i] for i in range(n) for j in range(n)), 'not symmetric' assert all(sum(H[i][k] * H[j][k] for k in range(n)) == (n if i == j else 0) for i in range(n) for j in range(n)), 'not Hadamard' def gamma(H): check_hadamard(H) n = len(H); V = [(a, b) for a in range(n) for b in range(n)] adj = [set() for _ in V] for x, (a, b) in enumerate(V): for y in range(x + 1, len(V)): c, d = V[y] if a != c and b != d and H[a][b] * H[b][c] * H[c][d] * H[d][a] == 1: adj[x].add(y); adj[y].add(x) return len(V), adj # ---------------------------------------------------------------- the graph on 306 vertices def delta(q): """Points of PG(4,q), Q = y0^2 + y1 y2 + y3 y4, l = . Vertices: the non-square points (Q(y) a non-square) and the q+1 points of l. l is a clique; y ~ P (P on l) iff B(y,P) = 0; for non-square y != z: y ~ z iff (B(y,z) = 0 and P(y) != P(z)) or z lies on the line , where P(y) = the point of l orthogonal to y.""" p = q Q = lambda y: (y[0] * y[0] + y[1] * y[2] + y[3] * y[4]) % p B = lambda y, z: (2 * y[0] * z[0] + y[1] * z[2] + y[2] * z[1] + y[3] * z[4] + y[4] * z[3]) % p def norm(y): for c in y: if c: inv = pow(c, p - 2, p); return tuple((inv * a) % p for a in y) sq = {(x * x) % p for x in range(1, p)} pts = sorted({norm(y) for y in itertools.product(range(p), repeat=5) if any(y)}) N = [y for y in pts if Q(y) and Q(y) not in sq] L = sorted({norm((0, a, 0, b, 0)) for a in range(p) for b in range(p) if (a, b) != (0, 0)}) att = {y: norm((0, y[4], 0, (-y[2]) % p, 0)) for y in N} # P(y): a1 y2 + a3 y4 = 0 V = N + L; idx = {v: i for i, v in enumerate(V)} adj = [set() for _ in V] def e(x, y): adj[x].add(y); adj[y].add(x) for i in range(len(N), len(V)): for j in range(i + 1, len(V)): e(i, j) for y in N: e(idx[y], idx[att[y]]) for i, y in enumerate(N): line = {norm(tuple((y[t] + s * att[y][t]) % p for t in range(5))) for s in range(p)} for j in range(i + 1, len(N)): z = N[j] if (B(y, z) == 0 and att[y] != att[z]) or z in line: e(i, j) return len(V), adj BUILDERS = { 'srg306_55_4_11': lambda: delta(5), 'srg400_171_74_72': lambda: gamma(paley2(9)), 'srg576_253_112_110': lambda: gamma(kron(paley2(5), [[1, 1], [1, -1]])), 'srg784_351_158_156': lambda: gamma(paley2(13)), 'srg1296_595_274_272': lambda: gamma(symplectic36()), 'srg1296_595_274_272_latin': lambda: gamma(latin36()), 'srg1296_595_274_272_paley': lambda: gamma(paley2(17)), 'srg1296_595_274_272_latinS3': lambda: gamma(latinS3()), } if __name__ == '__main__': out = sys.argv[1] if len(sys.argv) > 1 else 'out/new_srgs_multiorbit' names = sys.argv[2:] or list(BUILDERS) os.makedirs(out, exist_ok=True) for name in names: n, adj = BUILDERS[name]() with open(os.path.join(out, name + '.g6'), 'w', newline='\n') as fh: fh.write(to_g6(n, adj) + '\n') print(name, n, 'written', flush=True) \end{lstlisting} \end{document}