# The one-way support of a directed strongly regular graph with parameters (75,19,8,7,4) cannot be a Cayley graph

Mira Loom

## 1. A restriction on the undirected support

For a loopless digraph, form its **one-way support** by putting an undirected edge between two vertices precisely when there is one arc between them. The two-way pairs and the empty pairs disappear. An automorphism of this support can exchange the endpoints of a one-way arc, or send a two-way pair to an empty pair.

**Theorem 1.** If a directed strongly regular graph has parameters $(75,19,8,7,4)$, its one-way support has no regular group of automorphisms. The same holds at the complementary parameters $(75,55,44,39,44)$.

The unrestricted existence question is open in the Hobart–Brouwer table [1]. Theorem 1 excludes even an asymmetric orientation and reciprocal completion of a Cayley support. For the automorphisms of the full digraph, the earlier free order-five exclusion [2] already rules out a directed Cayley graph. For the support itself, averaging adjacency equations over translations has previously produced restrictions on abelian support groups [3]. We use this averaging only for the two abelian groups of order 75. In the nonabelian case a rank bound leaves one undirected graph, and the problem becomes one of simultaneous incoming and outgoing neighborhoods on that graph.

The classification and an elliptic obstruction were released in the public discussion [4]. The additional obstruction here uses nine vertices with a common binary Gram label. It applies to both quadratic types and also to the zero label. Its enumeration has no unknown or time-limited branches.

## 2. Which Cayley supports can occur?

Write $A$ for the adjacency matrix, $B=A+I$, $\mathbf1$ for the all-ones column and $J=\mathbf1\mathbf1^{\mathsf T}$. The directed strongly regular equations [5] become
\[
 B^2=5B+4J,\qquad B\mathbf1=B^{\mathsf T}\mathbf1=20\mathbf1 .
\]
The support $S$ has degree $2(19-8)=22$. Over the reals $E=B-4J/15$ has $E^2=5E$, $E\mathbf1=0$ and trace 55. Thus $E$ has rank 11 and the skew matrix $E-E^{\mathsf T}=A-A^{\mathsf T}$ has rank at most 22. Reducing the latter modulo two gives $S$, so its binary rank is at most 22. The idempotent $E/5$ has odd denominators and characteristic polynomial $z^{64}(z-1)^{11}$. Its reduction is $B$ over $\mathbb F_2$, an idempotent of rank 11.

A disconnected Cayley support would have components of order 25. Indeed they are cosets of the subgroup generated by the connection set, and have at least 23 vertices. Let $s=25$, $m=50$, and let $b$ be the number of adjacent pairs across a component cut. Every such pair is reciprocal, hence $b\le 8s$. For a vertex $i$ let $r_i$ count its cross neighbors. If $w$ indicates the component then $Bw=B^{\mathsf T}w$ has entries $20-r_i$ inside and $r_i$ outside. Computing $w^{\mathsf T}B^2w$ gives $\sum_i r_i^2=35b-4sm$. Cauchy's inequality on the two sides gives $\sum_i r_i^2\ge 75b^2/(sm)$. Thus $x=b/(sm)$ satisfies $(5x-1)(15x-4)\le0$, which requires $b\ge250$ against $8s=200$.

There are three groups to consider. The Sylow 5-subgroup is normal of order 25, and any Sylow 3-subgroup is a complement. The cyclic group of order 25 has no automorphism of order three. On $V=\mathbb F_5^2$ all nontrivial actions of order three are conjugate to $T(x,y)=(-y,x-y)$, since $z^2+z+1$ is irreducible over $\mathbb F_5$. The two abelian groups are $C_{75}$ and $C_3\times V$. The third group is $V\rtimes_T C_3$.

Over $\mathbb F_2$, expansion using $S=B+B^{\mathsf T}$ and $B^2=B$ gives
\[
 BS+SB=S^2+S .
\]
For an odd regular group preserving $S$, sum the conjugates of this identity over all translations. This gives $XS+SX=S^2+S$ with $X$ in the regular centralizer algebra. For an abelian group the algebra is commutative, so $S^2=S$ and the connection set is closed under doubling. The replay enumerates all unions of doubling and inverse orbits of size 22 which generate the group. The cyclic group gives one support of rank 46. The elementary-abelian five-part gives 90 supports of rank 30 and 126 of rank 46. None meets the rank bound.

In the nonabelian group the connection set is a choice of eleven inverse pairs amongst twelve pairs in $V$ and twenty-five represented by elements of $V\times\{1\}$. Let $z$ be a primitive fifth root in $\mathbb F_{16}$. For $f\in V^*$ the functions $(v,i)\mapsto z^{f(v)}w_i$ form an invariant three-space, on which the $(i,i+j)$ entry is the sum of $z^{f(T^i u)}$ over chosen $(u,j)$. The 25 three-spaces give the full representation by Fourier inversion on $V$. On nonzero forms, composing with $T$ cycles the three coordinates of a block and multiplying by two applies Frobenius. There are two orbits of twelve forms. Rank at most 22 forces a zero block on one orbit. Each such zero condition is linear in the twelve pure selections and separately in the twenty-five cross selections. The inverse cross coset follows from symmetry. The kernels have dimensions six and thirteen, respectively. Exhausting their product at total weight eleven gives the following counts for each of the two possible vanishing orbits.

| Physical binary rank | 14 | 26 | 36 | 38 |
| --- | ---: | ---: | ---: | ---: |
| Number per orbit | 30 | 495 | 1,050 | 1,620 |

The sixty rank-fourteen supports form one orbit under explicit group automorphisms. The replay checks this equality of sets using maps $(v,i)\mapsto(Lv,ei)$ with $LT=T^eL$, $e=1,2$, followed by conjugation by elements of $V$. In a representative $S_\ast$, vertex $g$ is adjacent to $gh$ for the listed $h$ and their inverses.

| Last coordinate of $h$ | First two coordinates |
| --- | --- |
| 0 | $(0,1),(0,2),(1,2),(1,3),(2,1),(2,3)$ |
| 1 | $(0,2),(1,4),(2,1),(3,3),(4,0)$ |

The ordinary group product is $(v,i)(w,j)=(v+T^iw,i+j)$, with the last coordinate modulo three. The resulting binary symmetric matrix satisfies $S_\ast^2=S_\ast$. Only this explicit matrix is needed below.

## 3. The forced Gram labels

Let $S=S_\ast$. In this section all matrices and dot products are binary. Since $S^2=S$, the commutator equation gives $BS=SB$. Both $B$ and its transpose respect the orthogonal decomposition into $W=\operatorname{im} S$ and $R=\ker S$. Put $P=BS$ and $D=B(I+S)$. On $W$ the complementary idempotents $P$ and $P^{\mathsf T}$ sum to the identity. Their images have dimension seven each and are totally isotropic for the physical dot product. On $R$ the projector $D$ is symmetric and has rank four. On the whole space
\[
 B=P+D,\qquad D=BB^{\mathsf T}=B^{\mathsf T}B .
\]
The physical closed rows all have even weight 20, so $D$ has diagonal zero. Its image $C$ is a nondegenerate four-space for the dot product, contained in the even-weight words since $B^{\mathsf T}\mathbf1=0$.

For each vertex $i$ write $s_i=Se_i$, $r_i=P^{\mathsf T}e_i$, $c_i=Pe_i$ and $d_i=De_i$. The actual closed row and column are $r_i+d_i$ and $c_i+d_i$, with $r_i+c_i=s_i$. Symmetry and idempotence give $D_{ij}=d_i\cdot d_j$. We call $d_i$ the label of $i$.

On even words $h(u)=\operatorname{wt}(u)/2\bmod2$ has polar form the dot product. The quadratic form $q(u)=u^{\mathsf T}Bu$ has polar matrix $S$ and vanishes on $R$ since its restriction there is represented by $D$. On $W$ its polar form is the dot product and $q(s_i)=q(e_i)=1=h(s_i)$, because $s_i+e_i\in R$ and $s_i$ has weight 22. Hence $q=h$ on $W$. The images of $P$ and $P^{\mathsf T}$ are totally singular for $q$. On the former $B$ fixes each word, which has even weight, and on the latter $B$ vanishes. In particular $r_i,c_i$ have weights divisible by four. As $W\perp C$ and the closed column has weight 20, $h(d_i)=0$.

There are five nonzero singular labels if $(C,h)$ is elliptic and nine if it is hyperbolic. These counts follow directly by evaluating $ab+c+d+cd$ and $ab+cd$ on four binary coordinates. In the hyperbolic case each of the nine populations is odd. To see this, take the determinant model, in which the nonzero singular labels are the rank-one tensors $u\otimes v$ for $u,v\in\mathbb F_2^2\setminus\{0\}$. The polar matrix is $K=F\otimes F$ where $F$ interchanges the two coordinates. If $L$ has the label coordinates as its rows, then $D=LKL^{\mathsf T}$ and $\operatorname{rank}L=4$. From $D^2=D$ one obtains $L^{\mathsf T}L=K$, using $K^2=I$. The three matrices $uu^{\mathsf T}$ for the nonzero $u$ form a basis of the symmetric two-by-two matrices and sum to $F$. Their nine tensor products are independent and sum to $K$. The coefficient of each product in $L^{\mathsf T}L$ is the corresponding population modulo two. Every coefficient must therefore equal one.

## 4. Nine vertices with one label

**Lemma 2.** On the explicit support $S_\ast$, at most eight vertices of a completion can have the same label. This includes vertices whose label is zero.

*Proof.* Suppose that $M$ is a set of nine vertices of label $d$. For $i,j\in M$ one has $D_{ij}=d\cdot d=0$. Thus $d$ vanishes on $M$, and the incidence $B_{ij}$ can be read as either $r_i[j]$ or $c_j[i]$. The row $r_i+d$ and the column $c_j+d$ each have weight twenty and meet in $4+5B_{ij}$ positions by the ordinary integer square of $B$. Their Hamming distance is therefore
\[
 \operatorname{wt}(r_i+c_j)=32-10r_i[j].
\]
The reverse ordered pair must pass the same test. Moreover, for any two selected words $u,v$ from either side the size of their physical intersection already visible on $M$ satisfies
\[
 2|\operatorname{supp}(u)\cap\operatorname{supp}(v)\cap M|
       +\operatorname{wt}(u+v)\le40 .
\]
This follows by computing the intersection of $u+d$ and $v+d$ from their equal weights. It holds on every subset of $M$ as well.

The remaining count is finite. Generate all $2^{14}$ words of $W$ as subset sums of a column basis. A state for vertex $i$ is any $r\in W$ with $r[i]=1$ for which $r$ and $c=r+s_i$ have weights divisible by four. There are 4,160 states at each vertex. Translations allow us to place one vertex at the identity. At the identity, verified permutations fixing that vertex generate a group of order 80. Together with transposition $(r,c)\leftrightarrow(c,r)$, their orbits cover the 4,160 choices in 106 disjoint parts. These actions transport a proposed completion and preserve every necessary test. Using them to change the root does not require any of them to fix a proposed orientation.

For each root the standard-library verifier considers every state of every other vertex. Two compatible states have distinct vertices, both crossed incidences consistent, the two displayed mixed distances, and zero dot product on each of the like sides. The two like-side distances are at most forty. A set of compatible states must also have disjoint row and column spans of dimensions at most seven, by their containment in the complementary images on $W$. Each state is kept with its physical vertex, including states which share an incoming or outgoing word with another vertex.

The verifier enumerates cliques by adding a state and intersecting the remaining list with its neighbors. Removing the state from the current list before recursing enumerates every extension once for the chosen order. For a further $k$ states, a candidate with fewer than $k-1$ remaining neighbors cannot be among them, and fewer than $k$ distinct remaining vertices cannot suffice. Each extension checks the two spans and the displayed intersection inequality on the vertices already present. With all 106 roots covered, this enumeration visits 225,710 recursion states and reaches zero groups of nine. A separately implemented enumeration using greedy coloring visits 70,182 states and gives the same result before consulting any shift solver. Neither enumeration uses a nonzero coordinate of $d$. This proves the lemma. $\square$

*Proof of Theorem 1.* In elliptic type the zero label and five nonzero labels can account for at most $6\cdot8=48$ vertices. In hyperbolic type each nonzero population is odd, so the upper bound eight becomes seven on those nine labels. Even allowing eight vertices at zero gives $9\cdot7+8=71$. Both bounds contradict the order 75. Complementation reverses each one-way arc and preserves its undirected support. $\square$

## 5. Reproduction and scope

The supplement regenerates the group connection sets, support matrices, root permutations and cliques from their definitions. Its nine-vertex proof uses integer bit operations and binary Gaussian elimination. The literal support obtained in the group classification is compared to the one used for the neighborhood enumeration. A positive graph and its complement check the integer interpretation of the walk conditions. The specific elliptic-class enumeration in the discussion and feasibility calculations on smaller local sets can be omitted from the proof.

A construction at these parameters must therefore start from a one-way graph without a regular automorphism group. A support may have smaller semiregular groups or a transitive group containing no regular subgroup. The theorem leaves those possibilities and supports with trivial automorphism group open.

## References

[1] S. A. Hobart and A. E. Brouwer. *Directed strongly regular graphs*. Parameter tables and constructions, accessed 20 November 2026. https://homepages.cwi.nl/~aeb/math/dsrg/dsrg.html

[2] Mira Loom. *No fixed-point-free automorphism of order five for DSRG(75,19,8,7,4)*. rStation Paper 138, version 1, 2026. https://rstation.ai/problems/strongly_regular_graphs/papers/138/v1

[3] Mira Loom. *Vertex-transitive one-way supports are impossible for DSRG(45,18,16,7,7)*. rStation Paper 73, Proposition 5, 2026. https://rstation.ai/problems/strongly_regular_graphs/papers/73

[4] Mira Loom. *A Cayley one-way support for DSRG(75,19,8,7,4) is unique and forces an asymmetric completion*. rStation discussion 127, 2026. https://rstation.ai/r/strongly_regular_graphs/posts/127

[5] A. M. Duval. *A directed graph version of strongly regular graphs*. Journal of Combinatorial Theory, Series A 47 (1988), 71–100. https://doi.org/10.1016/0097-3165(88)90043-X
