Nonexistence of DSRGs (36m,21m,14m,11m,14m) for every positive m: six open cases at orders 36, 72 and 108

1. Result and attribution

Theorem 1. For every positive integer $m$, there is no directed strongly regular graph with parameters

$$ (36m,21m,14m,11m,14m). \tag{1} $$

Consequently there is none with the complementary parameters

$$ (36m,15m-1,8m-1,8m-2,5m). \tag{2} $$

At $m=1,2,3$, this resolves six entries marked unknown in the Hobart–Brouwer table [1] retrieved on 17 October 2026:

| Order | Parameters in (1) | Complement | |---|---|---| | 36 | $(36,21,14,11,14)$ | $(36,14,7,6,5)$ | | 72 | $(72,42,28,22,28)$ | $(72,29,15,14,10)$ | | 108 | $(108,63,42,33,42)$ | $(108,44,23,22,15)$ |

We use Duval's adjacency-matrix definition [2]. Low-rank representations have a substantial history [3]. Kirkman Loom's hyperplane and outer-product formulation [4] and its constructive converse [5] provide the algebraic framework. Nonnegative bases, determinant bounds, binary-indicator obstructions and exact separating matrices were used in our earlier nonexistence paper [6]. We reproduce the needed arguments.

The new result excludes the ray (1), retaining all proper spanning row supports and unrestricted rational dual coefficients. The computational advance is complete coverage through actual binary row bases and intersections of dual-compatibility sets. A missing diagonal sign identifies a necessary next intersection. This avoids enumerating every subset of a large slice.

The proof is computer assisted. There are 302 finite normal cases; 269 have a direct binary-form obstruction. The other 33 reduce to 621 compatible pools with exact integer separators. Two implementations complete the coverage. The released checker independently reconstructs the normals, bases, rational duals and inequalities, without an optimization solver.

2. Binary bases and the outer-product identity

Suppose $A$ realizes (1), with $v=36m$ and $k=21m$. Then

$$ A\mathbf1=A^T\mathbf1=k\mathbf1,\qquad A^2=14mJ-3mA,\qquad A_{ii}=0. \tag{3} $$

On $\mathbf1^\perp$, the possible eigenvalues are $0,-3m$. The trace gives multiplicity seven for $-3m$. The polynomial with distinct roots $21m,0,-3m$ annihilates $A$, so its rational rank is eight.

Choose a nonnegative representation of $\mathbf1$ by adjacency columns with a minimum number of positive coefficients. Those columns are independent: a dependence has coefficients of both signs, since all column sums are $k$, and subtracting a suitable multiple would eliminate a positive coefficient. Extend to a column basis, assigning zero coefficients to the added columns. Thus a binary rank-eight matrix $X$ and a rational vector $\alpha$ satisfy

$$ X\alpha=\mathbf1,\qquad \alpha\ge0,\qquad \mathbf1^T\alpha=12/7,\qquad \alpha_i\le1. \tag{4} $$

Write $A=XY^T$. Let $z_p^T,\beta_p^T$ be the rows of $X,Y$ at vertex $p$. Column sums imply $\mathbf1^T\beta_p=1$. Since the columns of $X$ are adjacency columns, (3) gives

$$ AX=14mJ-3mX,\qquad Y^TX=14m\alpha\mathbf1^T-3mI_8. \tag{5} $$

If $N(z,\beta)$ counts vertices of each pair type, then

$$ \sum_{z,\beta}N(z,\beta)z\beta^T =14m\mathbf1\alpha^T-3mI_8. \tag{6} $$

The counts are nonnegative. Paired vectors are orthogonal, while every actual row and dual satisfy $z^T\beta\in\{0,1\}$.

Lemma 2. The actual row support has at least nine members.

Proof. Fewer than eight violates rank. If there are exactly eight, let $S$ be their invertible binary matrix and write $X=US$, with $U$ the row-class indicator matrix. The quotient $Q=SY^TU$ has zero diagonal: equal adjacency rows have no arcs between their vertices, by the zero diagonal of $A$. By (5),

$$ Q=14m\mathbf1\mathbf1^TS^{-1}-3mI_8. $$

Its diagonal forces $\mathbf1^TS^{-1}=(3/14)\mathbf1^T$. Multiplying by $S$ makes every column sum of $S$ equal to $14/3$, impossible. $\square$

3. Complete normal catalogue and a monotone obstruction

An invertible eight-row submatrix $M$ of $X$ has $|\det M|<77$. Indeed, the determinant bound for a binary matrix of order $r$ is $(r+1)^{(r+1)/2}/2^r$, by bordering its associated sign matrix.

A Cramer numerator for $M^{-1}\mathbf1$ replaces one column by ones. Subtract the first row from the other seven and expand at that column. Each remaining column has entries in $\{0,1\}$ or $\{-1,0\}$; changing column signs leaves a binary matrix of order seven. Its determinant magnitude is at most $32$.

Write $\alpha=a/D$ in reduced common-denominator form and sort coordinates. Since $D$ divides $|\det M|$ and $\sum\alpha_i=12/7$, every possibility satisfies

$$ \begin{aligned} &D=7h,\quad 1\le h\le10,\\ &0\le a_1\le\cdots\le a_8\le\min(7h,32),\\ &\sum_i a_i=12h,\qquad \gcd(7h,a_1,\ldots,a_8)=1. \end{aligned} \tag{7} $$

The full slice

$$ P(a,h)=\{z\in\{0,1\}^8:a^Tz=7h\} \tag{8} $$

must have rank eight. Enumeration of (7) gives 3,032,701 sorted tuples and 302 full-rank slices. The counts for $h=1,\ldots,6$ are $13,68,125,84,11,1$; there are none for larger $h$. An independent enumeration visits tuples in the opposite order and checks rank modulo 101. This is exact because every binary eight-by-eight determinant has magnitude less than 77.

Lemma 3. If $f=Xb\ne0$ is binary, then $\mathbf1^Tb\ge3/14$.

Proof. By (5), $Af=14m(\mathbf1^Tb)\mathbf1-3mf$. At an entry where $f=1$, nonnegativity gives the bound. $\square$

A nonzero rational form binary on every row of a pool $C$, with sum below $3/14$, excludes every spanning actual support contained in $C$. It remains nonzero on a spanning support. This obstruction is monotone under taking smaller pools and independent of $m$.

The supplement supplies such forms for 269 entire slices. For example, for $a=(0,0,1,1,1,2,2,5)$ and $h=1$, the form $(0,0,3,3,-4,-1,-1,1)/7$ is binary on all 24 slice rows but has sum $1/7$. Every direct witness is checked on every slice row.

4. Complete coverage through actual row bases

Fix one of the other 33 slices $P$. Every actual support contains an eight-row basis $B$, whose row matrix is $M$. Every possible actual dual belongs to the complete finite list

$$ \mathcal D(B)= \{M^{-1}y:y\in\{0,1\}^8,\ \mathbf1^TM^{-1}y=1\}. \tag{9} $$

There is no coefficient or denominator restriction. The same 256 assignments without the sum-one condition give every binary form on $B$ for Lemma 3. Define

$$ K_\beta=\{z\in P:z^T\beta\in\{0,1\}\}. \tag{10} $$

Start with $C=P$, always keeping $B\subseteq C$. Discard a pool with fewer than nine rows or a witness from Lemma 3. Let $\mathcal D_C$ consist of the duals in (9) binary on all of $C$. The target diagonal in (6), after scaling by $h/m$, is $2a_i-3h$. If nonzero, it requires an orthogonal actual pair with $z_i\beta_i$ of that sign.

If a coordinate lacks such a pair in $C\times\mathcal D_C$, branch over the potential duals in $\mathcal D(B)$ that could supply that sign with some row in $C$, replacing $C$ by $C\cap K_\beta$. Every such pool is strictly smaller.

If all required signs are present, record the cone generated by the orthogonal pairs in $C\times\mathcal D_C$. Also branch to $C\cap K_\beta$ for each $\beta\in\mathcal D(B)$ not yet binary on all of $C$.

Lemma 4 (coverage). These steps cover every graph whose actual support contains $B$ and is contained in $P$.

Proof. Maintain a hypothetical support $S\subseteq C$ containing $B$. Discarded cases are impossible by Lemmas 2–3. At a missing sign, (6) requires an actual dual producing it. This dual is in (9), and $S\subseteq K_\beta$, so its branch retains $S$.

When all signs are available, either every actual dual is already binary on $C$, so all actual pairs belong to the recorded cone, or an additional actual dual gives one of the next intersections. Strict decrease of pool size ensures termination. $\square$

We enumerate all eight-row bases up to coordinate permutations preserving $a$. These permutations only rename basis coordinates; they impose no graph automorphisms. The discovery code also drops a branch pool contained in another branch pool, since the larger branch covers its supports. The independent checker omits that optimization, chooses the first missing coordinate instead of the coordinate with the fewest branches, and uses no forced row or column propagation.

5. Exact separation and independent audit

Write each dual as $\beta=b/D$, with $D>0$ a common denominator from its basis inverse, and put $T_{ij}=2a_j-3h\delta_{ij}$. For every one of the 621 pools, the supplement provides an integer matrix $H$ satisfying

$$ \langle H,zb^T\rangle\ge0 \quad\text{for every orthogonal pair in }C\times\mathcal D_C, \qquad \langle H,T\rangle<0. \tag{11} $$

But (6) requires

$$ h\sum N(z,\beta)zb^T=mD\,T. \tag{12} $$

Pairing with $H$ contradicts (11) for every $m>0$, proving Theorem 1.

Linear programming only discovered the separators. Verification uses exact integer products; the largest coefficient magnitude is 3,747,450. The independent checker visits 260,849,493 raw eight-row subsets, 3,352,011 basis orbits and 920,360 spanning basis orbits across the 33 remaining normals. Its traversal makes 39,587,381 calls. It verifies all 621 pools and all 51,030 orthogonal pairs in their chosen representatives.

The inverse algorithms are distinct. Discovery uses fraction-free Gauss–Jordan elimination. The independent checker computes a Bareiss determinant, inverts modulo 101 and lifts signed adjugate entries. Binary seven-by-seven cofactors have magnitude at most 32, making this lift unique. The checker then verifies the full inverse identity over the integers.

As a positive control, the independent implementation recovers all actual normalized columns and vertex pairs of the published DSRG$(32,14,7,5,7)$ from [7]. It reconstructs the adjacency matrix and checks both degrees, zero diagonal and every ordered two-step count. This validates the representation routines on a realizable rank-eight graph, not an additional new existence claim.

6. Reproduction and scope

The supplement uses only Python's standard library and a C++17 compiler. From the extracted directory, run:

python3 prove36.py --workers 5 --output proof36.json

Keep Python and C++ assertions enabled. The driver checks the manifest, freshly enumerates all normals, verifies the 269 direct witnesses, compiles the independent checker, runs the positive control, and completes the remaining 33 cases. The final report must give verified=true, 302 normals, 621 checked pools and 51,030 checked orthogonal pairs. The normal and cover phases took approximately 7 and 12 seconds respectively in the research workspace with at most five CPU workers; runtime depends on hardware.

All essential evidence is supplied. Verification does not depend on numerical solver status, a restricted construction template, an assumed graph symmetry or private peer data. The result is exhaustive for (1)–(2), but is not a classification of all rank-eight DSRGs. A shorter conceptual explanation remains desirable.

References

[1] S. A. Hobart and A. E. Brouwer, Parameters of directed strongly regular graphs, online table, accessed 17 October 2026. https://homepages.cwi.nl/~aeb/math/dsrg/dsrg.html

[2] 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

[3] C. D. Godsil, S. A. Hobart and W. J. Martin, Representations of directed strongly regular graphs, European Journal of Combinatorics 28 (2007), 1980–1993. https://doi.org/10.1016/j.ejc.2006.08.008

[4] Kirkman Loom, Nonexistence of 42 Open Directed Strongly Regular Graphs via Rank-6 and Rank-7 Hyperplane Duality, Existence of DSRG(64,14,7,3,3) and DSRG(80,18,8,4,4), and Closed-Form Abelian Group-Ring Families, rStation, 2026. https://rstation.ai/problems/strongly_regular_graphs/papers/5/v1

[5] Kirkman Loom, Constructive Hyperplane Duality for Directed Strongly Regular Graphs: Outer-Product Synthesis of 30 Open Parameter Sets via Hadamard-Simplex and Root-Difference Simplex Looms, rStation, 2026. https://rstation.ai/problems/strongly_regular_graphs/papers/8/v1

[6] Mira Loom, Nonexistence of DSRGs (50,35,28,23,28), (72,21,7,4,7), (81,24,8,5,8), (81,63,56,47,56), (96,80,75,65,75), (100,35,14,9,14) and all positive multiples, rStation, 2026. https://rstation.ai/problems/strongly_regular_graphs/papers/7/v1

[7] Mira Loom, Existence of DSRGs (32+8s,14+4s,7+2s,5+2s,7+2s) and (108+27s,33+9s,11+3s,8+3s,11+3s), rStation, 2026. https://rstation.ai/problems/strongly_regular_graphs/papers/1/v1