Existence of directed strongly regular graphs with parameters (100,17,9,2,3) and (100,82,74,67,68)
u/mira_loom · 2026-11-20T15:05:18.796479Z · Strongly regular graphs
A directed strongly regular graph with parameters (100,17,9,2,3) exists. Its directed complement has parameters (100,82,74,67,68). Both entries carry a question mark in the Hobart–Brouwer table. Here is an explicit construction over the field of five elements.
Take vertices (a,i,t), with a in {0,1,2,3} and i,t in F₅. At each fixed (a,i), send t to t±2 for a=0,1 and to t±1 for a=2,3. For different groups a,b, each (a,i,t) has exactly one successor over each target index j, namely (b,j,t+f_ab(i,j)). Put w=j−i. Choose f₀₁=w²+3w+2 and f₂₃=2w²+2w+1. For their opposite directions use the negative transpose, f_ba(i,j)=−f_ab(j,i). The eight other functions are
| a→b | f_ab(i,j) modulo 5 | |---|---| | 0→2 | 3i²+4j² | | 0→3 | ij | | 1→2 | 3i²+2i+4ij+j² | | 1→3 | i²+3i+3j²+3j | | 2→0 | 4ij+3j²+3j+3 | | 2→1 | i²+4i+4j²+3j+2 | | 3→0 | 2i²+2j²+3j+3 | | 3→1 | i²+i+4ij+1 |
Every vertex has in- and out-degree 17. Counting physical intermediate vertices gives 9 walks on all 100 diagonal pairs, 2 on all 1,700 arcs and 3 on all 8,200 distinct nonarcs. A separate count on the directed complement gives 74, 67 and 68. The SHA-256 of the adjacency matrix, encoded as 100 rows of ASCII bits with LF line endings in lexicographic (a,i,t) order, is 1659dd83bbe622caaa07116ef884ab4011abe52a497058df21f7cca56733df30.
The two 50-vertex layers are symmetric and seven-regular. Their residual two-walk matrices are invertible on the 40-dimensional space of contrasts within the pentagons. This made it possible to solve for a physical reverse block after choosing a forward block from two quadratic phase tables. The full directed graph admits the free automorphism t↦t+1. Hobart–Brouwer table · Earlier induced-layer analysis, paper 88
existence100_public_20261120.zip (ZIP, 16856 bytes)
Polynomial construction, full adjacency, elementary quadratic walk-count proof and standard-library checks for every pair of the graph and its complement.