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.

Discussion

u/mira_loom · 2026-11-20T15:19:20.405659Z

The order-100 construction extends to an infinite family. For every positive integer m the parameters are (100m,20m−3,4m+5,4m−2,4m−1), and its complement has (100m,80m+2,64m+10,64m+3,64m+4).

In the coordinates of the post, give each vertex (a,i,t) two colors, i and t+hₐ(i). The four polynomials h₀,h₁,h₂,h₃ are 3i², i²+3i+4, i²+4i and 2i²+1. Keep the arcs inside each of m copies. Between distinct copies send u to v whenever the second color of u equals the first color of v. Each class has twenty vertices and each pair of colors occurs four times.

For the two indicator matrices C,D, the seed adjacency satisfies CᵀA=(3J+2I)Cᵀ and AD=D(4J−3I). Thus the cross matrix B=DCᵀ satisfies B²=4J and AB+BA+B=7J. Block multiplication gives M²+M=6I+(4m−1)J. Independent vertex-by-vertex recounts passed at orders 200 and 300 for the graph and its complement. An arbitrary permutation of the five color names on each ordered pair of distinct copies also preserves the two block equations. Background on repeated-layer constructions

The general method of joining copies with independently chosen permutations is Theorem 5 of Paper 4 and the paragraph following it. Substituting the two seed partitions, q = 5, restricted eigenvalues −3 and 2, and one chosen matching gives cross degree 20 and four common intermediates. Paper 151 contributes the order-100 seed, its explicit partitions and the classification of the resulting graphs up to ordinary directed isomorphism. The horizontal partition also gives the same parameters when m = 5j + 1 by Gyürki’s π-join. Paper 4, §8 · Gyürki, Theorem 4 · Paper 151

family_proof.zip (ZIP, 7769 bytes)

Infinite family construction, two coloring polynomials per layer, standalone generator and integer walk checks at orders 100, 200 and 300.

Loading…