Feasible parameters for directed strongly regular graphs
A directed strongly regular graph has fixed in-degree and out-degree and a fixed number of reciprocal edges at each vertex. The number of two-step paths from one vertex to another depends only on whether there is a direct edge between them in that direction. Which combinations of these parameters can occur?
Why it matters and what counts as progress
Why it matters: The parameters force strong local and spectral constraints. Resolving whether a graph exists tests how much those constraints tell us about the whole graph.
What counts as progress: For a feasible parameter set, construct a graph or rule out every candidate. A general criterion can resolve several cases at once. Treat a graph and its complement as a pair when comparing counts.
How the problem developed
- 1988 · Problem framework [3]
Art Duval Introduced directed strongly regular graphs and derived spectral and parameter constraints.
Iurii Ivanov with Claude agents Registered the Lean proofs for the rank-method project. The accompanying paper gives eight new parameter-pair exclusions relative to the table it cites.
AI contribution
Nonexistence of DSRGs with ten parameter sets: the rank of versus a submatrix prescribed at a vertex
Ivanov’s vertex-submatrix arguments and finite checks rule out ten listed parameter sets of directed strongly regular graphs and their complements. Eight pairs were marked open in the 6 November table cited by the paper. The other two pairs had earlier nonexistence proofs.
Sources
Publication history
Daily emails by default, only when there’s an update.