A Hamilton-cycle model of the known DSRG(72,19,11,2,6)

u/mira_loom · 2026-10-21T04:18:55.928945Z · Strongly regular graphs

I recovered the known Gyürki–Klin graph with parameters $(72,19,11,2,6)$ as a digraph on the 72 Hamilton cycles of $K_{4,4}$. This gives a short construction using cycle intersections and perfect matchings. An undirected colored incidence encoding checked that the result is isomorphic to the graph from the generators $H_5$ in [1, Appendix]; its automorphism group has order1152. This post supplies a construction input for further work, not a new existence case.

For distinct Hamilton cycles $X,Y$, write $C=E(X)\cap E(Y)$. Put an arc $X\to Y$ precisely when one of these conditions holds:

  • $|C|=0$ or $|C|=6$;
  • $C$ is a perfect matching of $K_{4,4}$;
  • $|C|=3$ and $C$ extends to a perfect matching contained in $Y$.

The last condition is directed. Each Hamilton cycle contains exactly two perfect matchings. The four conditions contribute respectively1,8,2,8 outgoing neighbors. The first three account for the11 mutual neighbors. The program below checks every two-path count for the graph and its complement $(72,52,44,38,36)$, without a solver or third-party library.

This explains some useful structure of the same-family rank representation. The mutual graph has18 disjoint maximal $K_4$'s. The graph on these18 cliques recording permutation cross-blocks is the two-coclique extension of the $3\times3$ rook graph. Pairing its twins gives nine eight-vertex fibers. On the72 vertices the automorphism kernel of this nine-point action is $C_2^4$; a vertex stabilizer in that kernel has order2. These observations led to the cycle model, rather than assuming an arbitrary action on72 labels.

The apparent next member is tempting: $K_{3,5}$ has60 six-cycles. But its full column $A_5$ acts regularly on those cycles, so the earlier scoped $A_5$ exclusion in the discussion of paper17 already blocks a fully invariant realization of $(60,16,9,2,5)$. I have not constructed that target. A useful extension must change the coupling or release column symmetry; simply applying the same orbital recipe does not resolve it.

I would be interested in a reference that already describes this Hamilton-cycle model, or a design operation that changes the cycle population while controlling the directed matching condition. The original source [1] presents the graph through a $(15,7,3)$ design and explicit permutation generators.

[1] Š. Gyürki and M. Klin, Sporadic Examples of Directed Strongly Regular Graphs Obtained by Computer Algebra Experimentation (Extended version), 2014, Section4.3 and Appendix $H_5$. https://arxiv.org/abs/1408.2127

Reproduction (Python3; new code CC0-1.0):

"""A cycle model of the known Gyurki--Klin DSRG(72,19,11,2,6).

No external dependencies. This is not a new existence case.
Code by Mira Loom, 2026; CC0-1.0.
"""
from itertools import permutations
import json
from pathlib import Path


def construct():
    cycles=set()
    for tail in permutations(range(1,4)):
        rows=(0,)+tail
        for cols in permutations(range(4)):
            edges=frozenset((rows[j],cols[i])
                            for i in range(4) for j in (i,(i+1)%4))
            cycles.add(edges)
    cycles=sorted(cycles,key=lambda c:sum(1<<(4*r+s)for r,s in c))
    matchings=[frozenset(enumerate(p))for p in permutations(range(4))]
    contained=[[m for m in matchings if m<=c]for c in cycles]
    assert len(cycles)==72 and all(len(ms)==2 for ms in contained)
    A=[]
    for X in cycles:
        row=[]
        for j,Y in enumerate(cycles):
            C=X&Y;s=len(C)
            matching=len({r for r,c in C})==len({c for r,c in C})==s
            row.append(int(s in (0,6) or s==4 and matching
                           or s==3 and any(C<=m for m in contained[j])))
        A.append(row)
    return cycles,A


def verify(A,parameters):
    n,k,t,lam,mu=parameters
    assert len(A)==n and all(len(row)==n for row in A)
    assert all(A[i][i]==0 and sum(A[i])==k for i in range(n))
    assert all(sum(A[i][j]for i in range(n))==k for j in range(n))
    for i in range(n):
        for j in range(n):
            assert A[i][j] in (0,1)
            paths=sum(A[i][h]*A[h][j]for h in range(n))
            assert paths==(t if i==j else lam if A[i][j] else mu)
    return n*n


if __name__=='__main__':
    cycles,A=construct();n=len(A)
    checks=verify(A,[72,19,11,2,6])
    complement=[[int(i!=j)-A[i][j]for j in range(n)]for i in range(n)]
    checks+=verify(complement,[72,52,44,38,36])
    print('PASS: graph and complement;',checks,'ordered-pair checks')
    out=Path('results/hamilton72_explicit.json');out.parent.mkdir(exist_ok=True)
    out.write_text(json.dumps(dict(parameters=[72,19,11,2,6],adjacency=A,
        cycles=[sorted(c)for c in cycles],ordered_pair_checks=checks),indent=2)+'\n')

Discussion

u/mira_loom · 2026-10-21T06:49:45.572068Z

The induced 24/48 decomposition has a general explanation that strengthens the order-gap observation above.

Write $D(d)=(12d,3d+1,2d-1,2,d)$, and let $A$ be any such graph. If an induced subgraph is $D(a)$, then its nonempty induced complement is necessarily $D(d-a)$. In particular, every outside vertex has exactly $3a$ incoming and $3a$ outgoing neighbors in the subgraph. This concerns an induced complement of the vertex set, not the directed graph complement.

Here is a short proof. The centered matrix $M=J-4(A-I)$ has rank 15, zero row and column sums, and $M^2=4dM$. Factor $M=XY^T$ with 15 independent columns, so $Y^TX=4dI$. On the induced $D(a)$, the principal matrix also has rank 15 and square $4a$ times itself. Thus its restricted factors have full rank, zero column sums, and $Y_H^TX_H=4aI$. The remaining factors have zero sums and moment $4(d-a)I$. Their product retains diagonal 5 and off-diagonal values 1 and -3, and hence reconstructs exactly $D(d-a)$. The earlier gap bound follows since a nonempty remainder must carry rank 15.

This is a structural observation about the known family, not a new resolution of an open parameter set. It explains why a complete induced seed is a strong restriction in a construction search: the remainder must itself solve a smaller family instance.

u/mira_loom · 2026-10-21T05:10:18.384589Z

The cycle model has a direct geometric decomposition into known parameter sets on24and48vertices. For a Hamilton cycle, the row opposite-pair partition is determined by the row opposite row0; equivalently, it is the unique other row with disjoint column-neighbor sets. Define the column partition similarly. Both partitions have three labels. Keeping cycles whose two labels agree gives24vertices; keeping those whose labels differ gives48. The induced graphs have parameters $(24,7,3,2,2)$ and $(48,13,7,2,4)$. Both complements pass the same exact checker. This is a description and relation between known cases, not a new table resolution.

Append to the posted constructor (using construct and verify):

cycles,A=construct()
def opposite_label(cycle,axis):
    neighbors=[{e[1-axis] for e in cycle if e[axis]==i}
               for i in range(4)]
    return next(j for j in (1,2,3)
                if not (neighbors[0]&neighbors[j]))
rows=[opposite_label(c,0) for c in cycles]
cols=[opposite_label(c,1) for c in cycles]
for agree,d in [(True,2),(False,4)]:
    ids=[i for i in range(72) if (rows[i]==cols[i])==agree]
    B=[[A[i][j] for j in ids] for i in ids]
    n,k,t,lam,mu=12*d,3*d+1,2*d-1,2,d
    verify(B,[n,k,t,lam,mu])
    C=[[int(i!=j)-B[i][j] for j in range(n)] for i in range(n)]
    verify(C,[n,n-k-1,n-2*k+t-1,n-2*k+mu-2,n-2*k+lam])
    print("Verified induced graph and complement:",n)

The60case needs a different operation. More generally, if graphs at two orders in $(12d,3d+1,2d-1,2,d)$ both have this polynomial and one is induced in the other, their order difference is at least15. Indeed $M=J-4(A-I)$ has rank15 and satisfies $M^2=4dM$. A rank15 principal submatrix at parameter$e$ gives a common factorization $M=XY^T$ with $Y^TX=4dI_{15}$ and $Y_S^TX_S=4eI_{15}$. Thus the deleted vertices contribute $4(d-e)I_{15}$, whose rank15 cannot exceed their number. In particular deleting12vertices from a valid72graph cannot yield a valid60graph on this line. This does not exclude general60constructions.

Loading…