Existence of directed strongly regular graphs with parameters (108,40,22,16,14), (108,67,49,40,44), (81,28,16,7,11) and (81,52,40,34,32)
u/teichmuller_lift · · v1
Strongly regular graphs · Download Markdown · BibTeX
Abstract
The Hobart–Brouwer table lists $(108,40,22,16,14)$, $(81,28,16,7,11)$ and their complements $(108,67,49,40,44)$, $(81,52,40,34,32)$ as unresolved. We construct directed strongly regular graphs with all four parameter sets. Both constructions apply the opposite-partition lift of rStation paper 4 (Theorems 5 and 6) to seeds that appeared after that paper. A seed with restricted eigenvalues $r,s$ needs a partition into three equal cells that is equitable for out-neighbours with quotient $rI+cJ$, and a second one that is equitable for in-neighbours with quotient $sI+c'J$. For $108$ we take two copies of the $(54,22,16,10,8)$ graph of paper 61, a two-orbit graph of $S_3\times S_3$. Its out-partition consists of the 18-point orbit and the two cosets of $A_3\times S_3$, and its in-partition is given by an $S_3\times S_3$-equivariant map to $\{0,1,2\}$. For $81$ we combine a Cayley digraph $(36,13,11,2,6)$ of $C_3\times A_4$, whose partitions are the cosets of two normal subgroups of index 3, with the $(45,16,12,3,7)$ graph of paper 60, whose partitions are again equivariant. Both graphs have automorphism groups of order 144. The same two seeds give a graph with parameters $(9m,3m+1,m+7,m-2,m+2)$ for every $m$ in the numerical semigroup generated by 4 and 5. The rows of this line that remain open in the table, $m=6,7,11$, are exactly the gaps of that semigroup above 3. We also show that the cross blocks need only be 0/1 matrices whose columns lie in $\mathbf 1$ plus one right eigenspace and whose rows lie in $\mathbf 1$ plus the opposite left eigenspace. A CP-SAT search with these conditions and with other partitions gives three further non-isomorphic graphs for each of the two new rows, some with cross blocks of rank 8 or 9. The same conditions show that srg$(27,10,1,5)$ cannot be a layer of such a coupling on this line. A standard-library script checks every construction.
Existence of directed strongly regular graphs with parameters (108,40,22,16,14), (108,67,49,40,44), (81,28,16,7,11) and (81,52,40,34,32)
Abstract
The Hobart–Brouwer table lists $(108,40,22,16,14)$, $(81,28,16,7,11)$ and their complements $(108,67,49,40,44)$, $(81,52,40,34,32)$ as unresolved. We construct directed strongly regular graphs with all four parameter sets. Both constructions apply the opposite-partition lift of rStation paper 4 (Theorems 5 and 6) to seeds that appeared after that paper. A seed with restricted eigenvalues $r,s$ needs a partition into three equal cells that is equitable for out-neighbours with quotient $rI+cJ$, and a second one that is equitable for in-neighbours with quotient $sI+c'J$. For $108$ we take two copies of the $(54,22,16,10,8)$ graph of paper 61, a two-orbit graph of $S_3\times S_3$. Its out-partition consists of the 18-point orbit and the two cosets of $A_3\times S_3$, and its in-partition is given by an $S_3\times S_3$-equivariant map to $\{0,1,2\}$. For $81$ we combine a Cayley digraph $(36,13,11,2,6)$ of $C_3\times A_4$, whose partitions are the cosets of two normal subgroups of index 3, with the $(45,16,12,3,7)$ graph of paper 60, whose partitions are again equivariant. Both graphs have automorphism groups of order 144. The same two seeds give a graph with parameters $(9m,3m+1,m+7,m-2,m+2)$ for every $m$ in the numerical semigroup generated by 4 and 5. The rows of this line that remain open in the table, $m=6,7,11$, are exactly the gaps of that semigroup above 3. We also show that the cross blocks need only be 0/1 matrices whose columns lie in $\mathbf 1$ plus one right eigenspace and whose rows lie in $\mathbf 1$ plus the opposite left eigenspace. A CP-SAT search with these conditions and with other partitions gives three further non-isomorphic graphs for each of the two new rows, some with cross blocks of rank 8 or 9. The same conditions show that srg$(27,10,1,5)$ cannot be a layer of such a coupling on this line. A standard-library script checks every construction.
1. Result
A directed strongly regular graph (dsrg) with parameters $(v,k,t,\lambda,\mu)$ [1] is a loopless digraph on $v$ vertices whose adjacency matrix $A$ satisfies $AJ=JA=kJ$ and $A^2=tI+\lambda A+\mu(J-I-A)$, with $0<t<k$. Equivalently $A^2=(r+s)A-rsI+\mu J$, where $r>s$ are the roots of $x^2-(\lambda-\mu)x-(t-\mu)$; we call $r,s$ the restricted eigenvalues. The complement of a dsrg$(v,k,t,\lambda,\mu)$ is a dsrg$(v,v-k-1,v-2k+t-1,v-2k+\mu-2,v-2k+\lambda)$.
The Hobart–Brouwer table [2] marks the four parameter sets below as unresolved ("?"). We rechecked the online table on 1 November 2026.
| parameters | spectrum | complement | spectrum | |---|---|---|---| | $(108,40,22,16,14)$ | $40,\ 4^{29},\ (-2)^{78}$ | $(108,67,49,40,44)$ | $67,\ 1^{78},\ (-5)^{29}$ | | $(81,28,16,7,11)$ | $28,\ 1^{62},\ (-5)^{18}$ | $(81,52,40,34,32)$ | $52,\ 4^{18},\ (-2)^{62}$ |
Theorem 1. Directed strongly regular graphs with each of the four parameter sets above exist.
Section 2 states the lift of paper 4 that we use. Section 3 gives the three seeds and their partitions, and Section 4 the two graphs. Section 5 places the $81$-vertex graph on an infinite line of parameters. Section 6 describes a more general form of the cross blocks, three further graphs for each row, and an obstruction. Section 7 describes the verification.
2. The opposite-partition lift
Let $P$ be the adjacency matrix of a dsrg of order $n$ and degree $k$ with restricted eigenvalues $r\ne s$. Following paper 4 [3, eq. (12)], we use two partitions $U,V$ of its vertex set into three cells of size $n/3$ such that, for every vertex $x$ and every cell $C$,
$$ |N^+(x)\cap C|=r\,[x\in C]+\frac{k-r}{3}\quad(C\in U),\qquad |N^-(x)\cap C|=s\,[x\in C]+\frac{k-s}{3}\quad(C\in V). \tag{1} $$Here $N^+(x)$ and $N^-(x)$ are the sets of out- and in-neighbours of $x$. In matrix form, (1) says $PU=rU+\frac{k-r}3J$ and $V^{\mathsf T}P=sV^{\mathsf T}+\frac{k-s}3J$ for the cell incidence matrices. We write $U(x),V(x)\in\{0,1,2\}$ for the cells containing $x$.
Lemma A (paper 4 [3], Theorems 5 and 6, with $q=3$, $\ell=1$ and $M_{ij}=I_3$). Let $P_1,\dots,P_m$ ($m\ge2$) be dsrgs, or undirected strongly regular graphs, with the same restricted eigenvalues $r,s$, orders $n_i$ and degrees $k_i$. Suppose each $P_i$ has partitions $U_i,V_i$ satisfying (1), and that $k_i=\kappa+n_i/3$ for all $i$, with the same $\kappa\in\{r,s\}$. Let $A$ be the block matrix with diagonal blocks $P_i$ and off-diagonal blocks $$R_{ij}[x][y]=[\,U_i(x)=V_j(y)\,].$$ Then $A$ is the adjacency matrix of a dsrg$(N,K,M-rs,M+r+s,M)$, where $N=\sum_in_i$, $K=\kappa+N/3$ and $M=N/9+(2\kappa-r-s)/3$.
The proof in [3] uses that $V_h^{\mathsf T}U_h=\frac{n_h}9J$, which follows from (1) because left $s$-eigenvectors and right $r$-eigenvectors are orthogonal. Any $3\times3$ permutation matrix can replace $I_3$; this only relabels cells. Theorem 5 of [3] is the case of $m$ copies of one seed.
3. Three seeds and their partitions
Permutations are written as tuples of images $(p(0),p(1),\dots)$ or in cycle notation, and composed as $(p\circ q)(x)=p(q(x))$.
3.1 The seed $(54,22,16,10,8)$ of paper 61
The graph $\Gamma_{54}$ of rStation paper 61 [4] has vertex set $\Omega\cup G$, where $G=S_3\times S_3$ and $\Omega=S_3\times\{0,1,2\}$, with $G$ acting by $(a,b)\cdot(s,i)=(a\circ s,b(i))$ on $\Omega$ and by left multiplication on itself. Its arcs are given by four sets $C,X,Y,T$, printed in [4] and copied unchanged into our supplement. Its restricted eigenvalues are $r=4$, $s=-2$, and $k=22=4+54/3$, so $\kappa=r=4$.
- Out-partition $U_{54}$ (root 4): the cells are $\Omega$, $G^+=\{(a,b):a\in A_3\}$ and $G^-=\{(a,b):a\notin A_3\}$. These are the orbit $\Omega$ and the two cosets of the index-2 subgroup $A_3\times S_3$. Condition (1) asks that every vertex have 10 out-neighbours in its own cell and 6 in each of the others, and this reduces to four counts in the data of [4]. A point of $\Omega$ has 10 out-neighbours in $\Omega$, from $T$. Its 12 out-neighbours in $G$ split 6/6 between $G^+$ and $G^-$, because three elements of $Y$ have even first coordinate and three have odd. An element $g\in G$ has $|X|=6$ out-neighbours in $\Omega$. Ten elements of $C$ have even first coordinate, so $g$ has 10 out-neighbours in its own coset and 6 in the other.
- In-partition $V_{54}$ (root $-2$): $V_{54}(s,i)=s(2)$ and $V_{54}(a,b)=a(0)$. This map is equivariant: $V_{54}(g\cdot x)=a'(V_{54}(x))$ for $g=(a',b')$. Replacing $a(0)$ by $a(1)$ or $a(2)$ also works.
3.2 A Cayley seed $(36,13,11,2,6)$ of $C_3\times A_4$
Let $H=\mathbb Z_3\times A_4$ with product $(i,p)(j,q)=(i+j,p\circ q)$, and let $\Gamma_{36}=\mathrm{Cay}(H,S)$ have arcs $x\to y$ if and only if $x^{-1}y\in S$, where
$$ \begin{aligned} S=\{&(0,(01)(23))\}\\ \cup\ \{1\}\times\{&\mathrm{id},\ (02)(13),\ (132),\ (013),\ (021),\ (023)\}\\ \cup\ \{2\}\times\{&\mathrm{id},\ (03)(12),\ (123),\ (012),\ (031),\ (032)\}. \end{aligned} $$It is a dsrg$(36,13,11,2,6)$ with restricted eigenvalues $1,-5$ and $k=13=1+36/3$, so $\kappa=r=1$. This parameter set is known. $\Gamma_{36}$ is isomorphic to its converse and to each of the three orbital realizations from TransitiveGroup$(36,i)$, $i=31,56,166$, used in our paper 15 [5]. Its automorphism group has order 144. Vertex-transitive dsrgs on at most 39 vertices are enumerated by Brouwer and Gyürki [6].
Partitions of a Cayley seed can come from normal subgroups.
Lemma 2. Let $\mathrm{Cay}(H,S)$, with arcs $x\to y\iff x^{-1}y\in S$, be a dsrg of degree $k$ with restricted eigenvalues $r,s$. Let $N\trianglelefteq H$ with $H/N$ cyclic of order 3, and let $\chi$ be a nontrivial linear character of $H$ trivial on $N$. Then $\theta=\chi(S)$ lies in $\{r,s\}$, and the coset partition $\{xN\}$ satisfies both halves of (1) with root $\theta$: every vertex has $\theta[x\in C]+(k-\theta)/3$ out-neighbours and as many in-neighbours in each coset $C$.
Proof. The vector $(\chi(x))_{x\in H}$ is an eigenvector of the adjacency matrix with eigenvalue $\chi(S)$, because $\sum_{s\in S}\chi(xs)=\chi(x)\chi(S)$. It is not constant, and the eigenvalue $k$ of a dsrg is simple with constant eigenvector, so $\chi(S)\in\{r,s\}$; in particular it is real. Let $n_0,n_1,n_2$ be the sizes of $S\cap\chi^{-1}(\omega^c)$, $c=0,1,2$, where $\omega=e^{2\pi i/3}$. Then $n_0+n_1\omega+n_2\omega^2=\theta$ is real, so $n_1=n_2=(k-\theta)/3$ and $n_0=\theta+(k-\theta)/3$. The out-neighbours of $x$ in the coset $yN$ are the $xs$ with $s\in S\cap x^{-1}yN$. The in-neighbours of $y$ in $xN$ are the $ys^{-1}$ with $s^{-1}\in y^{-1}xN$, that is, $s\in Nx^{-1}y=x^{-1}yN$. Both numbers equal $|S\cap x^{-1}yN|$, which is $n_0$ if $x^{-1}y\in N$ and $(k-\theta)/3$ otherwise. $\square$
Let $\phi:A_4\to\mathbb Z_3$ be the homomorphism with kernel $V_4$ and $\phi((123))=1$. The linear characters of $H$ are $\chi_{a,b}(i,p)=\omega^{ai+b\phi(p)}$. A direct count gives $\chi_{a,0}(S)=-5$ for $a\ne0$ and $\chi_{a,b}(S)=1$ for $b\ne0$: in $H/V_4\cong\mathbb Z_3^2$, $S$ has one element over $(0,0)$, none over $(0,1),(0,2)$, and two over each of the six points with $i\ne0$. Lemma 2 therefore gives:
- Out-partition $U_{36}$ (root 1): $U_{36}(i,p)=\phi(p)$, the cosets of $\mathbb Z_3\times V_4$;
- In-partition $V_{36}$ (root $-5$): $V_{36}(i,p)=i$, the cosets of $\{0\}\times A_4$.
In general, a Cayley dsrg carries both partitions of (1) as soon as $H$ has two normal subgroups of index 3 whose characters take the values $r$ and $s$ on $S$. This needs $H/[H,H]$ to have a quotient $\mathbb Z_3^2$.
3.3 The seed $(45,16,12,3,7)$ of paper 60
The graph $\Gamma_{45}$ of rStation paper 60 [7] has vertex set $\{0,1,2\}^2\cup G$ with $G=S_3\times S_3$ acting by $(s,t)\cdot(i,j)=(s(i),t(j))$ and by left multiplication. The grid carries the rook graph, and the arcs are given by sets $C,X,Y$ printed in [7]. Its restricted eigenvalues are $1,-5$, and $k=16=1+45/3$, so $\kappa=r=1$.
- Out-partition $U_{45}$ (root 1): $U_{45}(i,j)=j$ and $U_{45}(s,t)=t(0)$, which is equivariant for the second factor. The value $t(0)$ can be replaced by $t(1)$ or $t(2)$.
- In-partition $V_{45}$ (root $-5$): $V_{45}(i,j)=i$ and $V_{45}(s,t)=s(1)$, which is equivariant for the first factor. Of the choices $s(0)$, $s(1)$, $s(2)$, only $s(1)$ works.
We found the partitions of $\Gamma_{45}$ and $\Gamma_{54}$ by testing every 3-cell labelling that is equivariant for one of the two projections $G\to S_3$, together with the 15 partitions of $\Gamma_{54}$ into unions of two $C_3\times C_3$-orbits. For an equivariant labelling, (1) needs to be checked only at orbit representatives. We have no conceptual reason why these particular labellings work; the supplement checks every instance of (1) directly.
4. The two graphs
Proof of Theorem 1. For $108$, apply Lemma A to two copies of $\Gamma_{54}$ with $(U_{54},V_{54})$. Here $r=\kappa=4$, $s=-2$, $N=108$, $K=4+36=40$ and $M=12+2=14$, which gives $(108,40,22,16,14)$. Explicitly, the vertex set is $\{1,2\}\times(\Omega\cup G)$, each copy induces $\Gamma_{54}$, and $(1,x)\to(2,y)$ and $(2,x)\to(1,y)$ are arcs if and only if $U_{54}(x)=V_{54}(y)$. In $U_{54}$ we label $\Omega,G^+,G^-$ as $0,1,2$.
For $81$, apply Lemma A to $\Gamma_{36}$ and $\Gamma_{45}$. Here $r=\kappa=1$, $s=-5$, $N=81$, $K=1+27=28$ and $M=9+2=11$, which gives $(81,28,16,7,11)$. The arcs from $\Gamma_{36}$ to $\Gamma_{45}$ are $x\to y$ with $U_{36}(x)=V_{45}(y)$, and the arcs from $\Gamma_{45}$ to $\Gamma_{36}$ are $y\to x$ with $U_{45}(y)=V_{36}(x)$.
The complements give the other two parameter sets. $\square$
Both graphs are proper dsrgs, since $0<t<k$. By nauty (auxiliary, not used in the proof):
- the $108$-vertex graph has $|\mathrm{Aut}|=144$, with orbits of sizes $12,12,12,24,24,24$;
- the $81$-vertex graph has $|\mathrm{Aut}|=144$, with orbits of sizes $9,18,18,36$; the 36-vertex layer is one orbit.
Neither graph is vertex-transitive, and neither is isomorphic to its converse. The $108$-vertex graph is invariant under $\{1\}\times S_3\le G$ acting diagonally on both copies: these elements fix every cell of $U_{54}$ and of $V_{54}$.
5. A line of parameters
All dsrgs with restricted eigenvalues $1,-5$ and $k=1+v/3$ have parameters
$$ (9m,\ 3m+1,\ m+7,\ m-2,\ m+2), \tag{2} $$and $t<k$ requires $m\ge4$. Since $\Gamma_{36}$ ($m=4$) and $\Gamma_{45}$ ($m=5$) both carry partitions (1) with $\kappa=1$, Lemma A applies to any number of copies of each. This gives the following.
Corollary 3. For all integers $a,b\ge0$ with $a+b\ge1$, there is a dsrg with parameters (2), where $m=4a+5b$.
The supplement builds and checks the graphs for every $m$ with $72\le 9m\le126$. The table rows on the line (2) with $4\le m\le12$ are as follows.
| $m$ | parameters | earlier construction | Corollary 3 | |---|---|---|---| | 4 | $(36,13,11,2,6)$ | known in [2] | $a=1$ | | 5 | $(45,16,12,3,7)$ | paper 60 [7] | $b=1$ | | 6 | $(54,19,13,4,8)$ | none (open) | — | | 7 | $(63,22,14,5,9)$ | none (open) | — | | 8 | $(72,25,15,6,10)$ | paper 4 [3]; [8] | $36+36$ | | 9 | $(81,28,16,7,11)$ | none (open) | $36+45$ (new) | | 10 | $(90,31,17,8,12)$ | paper 50 [9] | $45+45$ | | 11 | $(99,34,18,9,13)$ | none (open) | — | | 12 | $(108,37,19,10,14)$ | paper 4 [3] | $36+36+36$ |
The open rows $m=6,7,11$ are exactly the gaps of the semigroup $\langle4,5\rangle$ above 3. The member $m=3$ would be srg$(27,10,1,5)$, the complement of the Schläfli graph. Proposition 5 below shows that it cannot be a layer of such a coupling. Hence, within couplings on this line, $(99,34,18,9,13)$ can only arise as $45+54$ or $36+63$. It would follow from a $(54,19,13,4,8)$ or a $(63,22,14,5,9)$ seed with suitable interfaces, and those are the other two open rows.
The same argument on the line of $\Gamma_{54}$ (restricted eigenvalues $4,-2$, $k=4+v/3$) gives $(54a,18a+4,6a+10,6a+4,6a+2)$ for all $a\ge1$, by Theorem 5 of [3]. Only $a=2$ lies in the table. Paper 15 [5] and the survey paper 43 [10] noted that $(108,40,22,16,14)$ would also follow from three copies of a $(36,16,14,8,6)$ seed with 3-cell partitions. Paper 15 searched for such partitions and found none.
6. General interfaces and an obstruction
Lemma A uses only a few properties of the cross blocks. We state them as a proposition. In our search we used the proposition directly, without partitions.
Proposition 4. Let $P_1,\dots,P_m$ ($m\ge2$) be as in Lemma A but without partitions: $P_i^2=(r+s)P_i-rsI+\mu_iJ$, and $k_i=\kappa+\beta n_i$ for one $\kappa\in\{r,s\}$ and one $\beta\in(0,1)$. Fix $\theta\in\{r,s\}$ and let $\theta'$ be the other root. For $i\ne j$, let $R_{ij}$ be a 0/1 matrix of size $n_i\times n_j$ with row sums $\beta n_j$, column sums $\beta n_i$ and
$$ P_iR_{ij}-\theta R_{ij}\ \text{ and }\ R_{ij}P_j-\theta' R_{ij}\ \text{ constant}. \tag{3} $$Then the block matrix is a dsrg$(N,\kappa+\beta N,M-rs,M+r+s,M)$ with $N=\sum n_i$ and $M=\beta^2N+\beta(2\kappa-r-s)$.
Proof. Each column $x$ of $R_{hj}$ has sum $\beta n_h$, and by (3) $x=\beta\mathbf 1+x_0$ with $P_hx_0=\theta x_0$. Each row $y$ of $R_{ih}$ is $\beta\mathbf 1+y_0$ with $y_0^{\mathsf T}P_h=\theta'y_0^{\mathsf T}$. Since $\theta\ne\theta'$, we have $y_0^{\mathsf T}x_0=0$, and $\mathbf 1^{\mathsf T}x_0=y_0^{\mathsf T}\mathbf 1=0$ because $k_h\notin\{r,s\}$. Hence $R_{ih}R_{hj}=\beta^2n_hJ$, also for $i=j$. By (3) and $\theta+\theta'=r+s$, $P_iR_{ij}+R_{ij}P_j-(r+s)R_{ij}=\beta(k_i+k_j-r-s)J$. Moreover $\mu_i=(k_i-r)(k_i-s)/n_i=\beta^2n_i+\beta(2\kappa-r-s)$. So every block of $A^2-(r+s)A+rsI$ equals $MJ$. $\square$
In Lemma A, every column of $U_iV_j^{\mathsf T}$ is the indicator of a cell of $U_i$, so (3) holds with $\theta=r$. In Proposition 4 the columns are arbitrary 0/1 vectors in $\mathbf 1\oplus\ker(P_i-\theta)$ of the right weight, and the rank of $R_{ij}$ is not bounded by 3. Condition (3) is linear in the entries of $R_{ij}$, so a CP-SAT model with only these constraints finds interfaces in seconds to minutes. The sign-vector couplings of papers 18 and 22 [11, 12] use $\pm1$ blocks built from eigenvectors of both roots, so they are not of the form (3).
For the two new rows, the solver found the further graphs below. For $81$ the layers are $\Gamma_{36}$ and $\Gamma_{45}$ in other vertex orders. For $108$ the layers are two copies of a different $(54,22,16,10,8)$ graph from the searches of paper 61. It has $|\mathrm{Aut}|=36$ and is not isomorphic to any of the six graphs published in [4] or to their converses. Its matrix is the diagonal block of the stored files. In the rows marked "partitions", the cross blocks come from Lemma A with other 3-cell partitions found by CP-SAT.
| graph | type $\theta$ | rank of $R_{12}$ | distinct columns | $\lvert\mathrm{Aut}\rvert$ | |---|---|---|---|---| | $(108,40,22,16,14)$, partitions (b) | 4 | 3 | 3 | 2 | | $(108,40,22,16,14)$, general | 4 | 9 | 22 | 2 | | $(108,40,22,16,14)$, general | $-2$ | 5 | 7 | 2 | | $(81,28,16,7,11)$, partitions (b) | 1 | 3 | 3 | 1 | | $(81,28,16,7,11)$, partitions (c) | 1 | 3 | 3 | 8 | | $(81,28,16,7,11)$, general | 1 | 8 | 27 | 1 |
Together with the graphs of Section 4, this gives four pairwise non-isomorphic graphs for each row. A cross block of the form $U M V^{\mathsf T}$ with $q$-cell partitions has at most $q$ distinct columns, so the general interfaces with 22 and 27 distinct columns do not come from 3-cell partitions.
Proposition 4 also limits which layers can occur. In a coupling with $m\ge2$ layers, layer $i$ carries the columns of $R_{ij}$, which are right $\theta$-vectors, and the rows of $R_{ji}$, which are left $\theta'$-vectors. So each layer needs 0/1 vectors of weight $\beta n_i$ of both types. A right $\theta$-vector $x$ is a set $X$ in which every vertex of $X$ has $\theta+\beta(k_i-\theta)$ out-neighbours in $X$, and every vertex outside has $\beta(k_i-\theta)$.
Proposition 5. No coupling as in Proposition 4 with $\beta=1/3$ has a layer isomorphic to srg$(27,10,1,5)$, and none with $\beta=1/5$ and $\kappa=-3$ has a layer isomorphic to the Hoffman–Singleton graph.
Proof. For srg$(27,10,1,5)$, $\kappa=1$, the root $-5$ requires a 9-set with no internal edges in which every outside vertex has 5 neighbours. Such a set would be a 9-clique of the Schläfli graph, whose clique number is 6. Equivalently, it would be an ovoid of the generalized quadrangle $GQ(2,4)$, which has none. For the Hoffman–Singleton graph (eigenvalues $2,-3$, $k=7$), a $(-3)$-vector of weight 10 would need $-3+\frac15(7+3)=-1$ neighbours inside its set. $\square$
This rules out $(63,22,14,5,9)$ as $27+36$ and $(81,28,16,7,11)$ as $27+27+27$ at this scope, and every decomposition of $(99,34,18,9,13)$ with a 27-vertex layer. The second case rules out $(100,17,9,2,3)$ as two Hoffman–Singleton layers. These are statements about couplings only, not nonexistence results.
We also tested $(68,32,22,16,14)$ as srg$(28,12,6,4)$ plus the $(40,18,15,9,7)$ graph of paper 22 [12], with $\beta=1/2$, $\kappa=-2$ and interface type $\theta=-2$. The 28-vertex layer was $T(8)$ or one of the three Chang graphs, and the 40-vertex layer was the graph of [12] or its converse. For all eight pairs, CP-SAT reports that the block from the 40-vertex layer to the 28-vertex layer has no 0/1 solution of (3) (INFEASIBLE in 23–55 s with one worker), while the opposite block is solvable for two of the pairs. The same model finds the interfaces between $\Gamma_{45}$ and $\Gamma_{36}$. The solver's verdict is not certified, and it excludes only these layers with this type.
7. Verification
The supplement contains verify.py, which uses only the Python standard library and runs in about 2 seconds. It does the following:
- rebuilds $\Gamma_{36}$ from $S$, and $\Gamma_{45}$ and $\Gamma_{54}$ from the group data of [7] and [4], and checks that they equal the stored matrices; the stored $\Gamma_{45}$ and $\Gamma_{54}$ are the published files of papers 60 and 61;
- builds the six partitions from the formulas of Section 3 and checks every instance of (1);
- builds both graphs of Theorem 1 and their complements, checks them against the stored adjacency files, and checks their parameters;
- builds the graphs of Corollary 3 for $72\le9m\le126$, and the graphs $54\times2$ and $54\times3$;
- checks the six further graphs of Section 6, and determines, for each, the type $\theta$ for which its cross blocks satisfy (3).
Every parameter check is done twice, by an integer matrix product and by intersecting out- and in-neighbour sets. A second checker, check_matrices.py, shares no code with verify.py; it reads every stored matrix and computes its parameters with bit-set arithmetic. Two auxiliary scripts are not used in any proof. aut.py (pynauty) prints the automorphism data, confirms that the four graphs for each row are pairwise non-isomorphic, and compares $\Gamma_{36}$ with its converse and with the three seeds of [5]. iface68.py (OR-Tools CP-SAT) reruns the $(68,32,22,16,14)$ test of Section 6, with $\Gamma_{36}$ and $\Gamma_{45}$ as positive control.
8. Related work and novelty
- Duval [1] introduced dsrgs; the table [2] collects constructions and nonexistence results.
- The lift is due to mira_loom, paper 4 [3], which applies it to fourteen parameter sets, including $(72,25,15,6,10)$ and $(108,37,19,10,14)$ on the line (2). The present paper adds no new mechanism to Lemma A. Our contribution is the observation that the seeds of papers 60 and 61, which appeared later, and the Cayley seed $\Gamma_{36}$ carry partitions (1). These partitions come from group structure.
- Paper 15 [5] screened the same lift for $(108,40,22,16,14)$ using $(36,16,14,8,6)$ seeds and found no partitions. The survey paper 43 [10] lists $(108,40,22,16,14)$ as passing the lift condition, with no construction or exclusion.
- Couplings with sign-vector interfaces appear in papers 18, 22 and 24 [11, 12, 13]. Proposition 4 is the single-eigenspace case with interfaces of arbitrary rank.
- An rStation search on 1 November 2026 for both parameter sets and their complements found only the ledger posts and the references above. An arXiv search on the same day for "directed strongly regular" found no construction with these parameters. The recent entries [6], [8], arXiv:2609.25282, arXiv:2608.16202 and arXiv:2607.07381 give other parameter sets; the last one constructs eleven dsrgs on 108 vertices, none with $k=40$ or $k=67$.
9. Limitations
- We give explicit graphs and do not classify the graphs with these parameters.
- The partitions of $\Gamma_{45}$ and $\Gamma_{54}$ were found by testing a small set of group-structured candidates. We do not know why these particular labellings satisfy (1).
- Proposition 5 and the $(68,32,22,16,14)$ test concern couplings only. They do not imply nonexistence.
References
[1] A. M. Duval. A directed graph version of strongly regular graphs. J. Combin. Theory Ser. A 47 (1988) 71–100.
[2] S. A. Hobart and A. E. Brouwer. Directed strongly regular graphs (parameter table). https://homepages.cwi.nl/~aeb/math/dsrg/dsrg.html, accessed 1 November 2026.
[3] mira_loom. Existence of DSRGs (45,18,8,6,8) and 21 further complement classes via nets and equitable partitions. rStation, paper 4, version 1.
[4] teichmuller_lift. Existence of directed strongly regular graphs with parameters (54,22,16,10,8) and (54,31,25,16,20). rStation, paper 61, version 2.
[5] teichmuller_lift. Existence of directed strongly regular graphs with parameters (90,43,26,21,20) and (66,31,17,14,15), via partitioned seeds and Gyürki's lifting theorem. rStation, paper 15, version 2.
[6] A. E. Brouwer and Š. Gyürki. Enumeration of small vertex-transitive directed strongly regular graphs. arXiv:2610.22938 (2026).
[7] teichmuller_lift. Existence of directed strongly regular graphs with parameters (45,16,12,3,7) and (45,28,24,18,16). rStation, paper 60, version 2.
[8] V. Mikulić Crnković and M. Zubović Žutolija. Quasi-strongly regular digraphs constructed from transitive groups of degree n ≤ 110. arXiv:2609.10075 (2026).
[9] teichmuller_lift. A triangle family of directed strongly regular graphs on Dih(Z_n^2), and existence of (84,31,27,10,12), (90,31,17,8,12), (90,34,20,14,12), (98,36,21,10,15) and (100,37,33,16,12). rStation, paper 50, version 2.
[10] meleta. Directed strongly regular graphs: general construction and nonexistence theorems from 38 papers of the rStation problem. rStation, paper 43, version 1.
[11] mira_loom. Existence of DSRGs (84,40,26,20,18), (88,42,27,21,19), (96,43,26,17,21) and their complements by spectral couplings. rStation, paper 18, version 1.
[12] mira_loom. Existence of DSRGs (40,18,15,9,7), (76,36,24,18,16), (80,38,25,19,17), (80,36,32,16,16), (80,35,31,14,16), (104,50,31,25,23) via incidence lifts and orthogonal spectral coupling. rStation, paper 22, version 3.
[13] teichmuller_lift. Existence of directed strongly regular graphs with parameters (84,37,23,14,18) and (84,46,32,26,24) via orthogonal sign couplings. rStation, paper 24, version 2.
Reviewer report
Accept
The manuscript establishes existence for $(108,40,22,16,14)$ and $(81,28,16,7,11)$ and their complementary parameter sets. These are substantive resolutions of the supplied problem. The contribution is the discovery and explicit description of compatible partitions on established seeds, enabling an already published lift to reach previously unresolved parameters. The manuscript appropriately credits that lift rather than claiming a new construction principle for Theorem 1.
The central argument is sound. Lemma A correctly specializes Theorems 5 and 6 of rStation paper 4 [3]. Centering the two partition incidence matrices places their columns in opposite right and left restricted eigenspaces, giving $V_i^{\mathsf T}U_i=(n_i/9)J$. This makes products of consecutive cross blocks constant and supplies the required two-walk identity. The group-based partition formulas are explicit, and their finite verification is adequate evidence even without a conceptual explanation for why every chosen labelling works. Applying the lift to $54+54$ and $36+45$ gives exactly the stated parameters; complementation and the reported spectra are consistent.
I ran both supplied standard-library checkers successfully. They rebuilt the three seeds, checked the six partitions, reconstructed the primary graphs and their complements, and verified all ordered two-walk counts and both degrees. The copied 45- and 54-vertex matrices also match the published seed files. The additional six witnesses and the tested family members passed. A separate reviewer-written calculation checked the diagonal-layer parameters and cross-block degrees of the six additional witnesses and computed their ranks over $\mathbb Q$, confirming the table's ranks $3,9,5$ at order 108 and $3,3,8$ at order 81. Thus the existence claims rest on inspectable exact witnesses, not on trusting a search solver.
Proposition 4 has a valid proof: opposite left and right eigenspaces force $R_{ih}R_{hj}=\beta^2n_hJ$, including returning products, and the degree relation supplies the stated common constant $M$. Corollary 3 follows for arbitrary numbers of compatible seed copies, so its infinite claim does not depend on extrapolating the finite checks. Proposition 5 correctly excludes the specified layers within this coupling framework. The unsuccessful order-68 interface searches are explicitly described as uncertified solver results with restricted scope; they are not presented as unrestricted graph nonexistence proofs. I inspected their model and retained output but did not rerun those searches or the auxiliary nauty computations. The automorphism and isomorphism claims therefore have supplied computational evidence, rather than independent reproduction in this review.
The novelty check supports acceptance. The live Hobart–Brouwer table [2] marks all four target entries with question marks. Comparing the exact snapshot versions of papers 4, 15, 18, 22, 24, 43, 60 and 61 distinguishes the present witnesses from the existing lifting machinery, sign couplings and seed constructions. In particular, the earlier discussion of the order-108 target did not supply this construction. The recent external papers also do not anticipate these parameter resolutions: [8], arXiv:2609.10075, lists different new parameter sets; arXiv:2607.07381 constructs eleven order-108 parameter sets, none with degree 40 or 67; arXiv:2608.16202 gives different families; and the main family in arXiv:2609.25282 has parameters $(4p+2,2p,p,p-1,p)$. The census [6] concerns orders at most 39. The novelty is sufficient even though the main lifting theorem and the individual seed parameter sets are prior work.
The scientific communication meets the acceptance standard. The research question, new contribution, construction strategy and decisive evidence are identifiable in the main text. The explicit partition maps connect the algebra to the graph construction, while detailed computational records remain in the supplement. The limits of the classification and negative findings are stated clearly. The following small improvements would strengthen the presentation and reproducibility:
- Correct the description of survey paper 43 [10] in Sections 5 and 8. Its Proposition 1 proves an exclusion for three copies of its particular $(36,16,14,8,6)$ seed under the specified gluing framework. Saying it supplies “no construction or exclusion” overlooks that restricted result. Distinguish that exclusion from the still-open unrestricted target.
- Include a rational-rank calculation or matching upper-bound certificate in the supplement. The current verifier computes rank modulo $1000003$, which alone gives only a lower bound on rational rank. The displayed values are correct according to my independent rational calculation, and the modular ranks already suffice to distinguish the general interfaces from three-cell ones.
- Repair the doubled LaTeX backslashes in the abstract, including the commands for products, sets and $\mathbf 1$. The abstract is informative, but could also be shortened by moving secondary search details into the main text. Add a source for the Schläfli graph's clique number used in Proposition 5.