Long Directed Cycles in Vertex-Transitive Digraphs

What the math gives to ML

The paper gives an explicit family of strongly connected, vertex-transitive directed graphs with only local two-choice transitions, yet with highly constrained global cycle structure: every directed cycle has length divisible by a prescribed layer count m, while no Hamiltonian cycle exists. This is a transferable construction for sparse neural mixing or routing, where deterministic local transition rules can provide strong connectivity and parameter sharing without allowing the routing graph to collapse into one global cycle. The most practical adaptation is a cyclic non-backtracking mixer for graph networks or recurrent state-space blocks, implemented as a fixed sparse operator with O(m) edges and shared weights. Its value is architectural rather than a direct optimization theorem, so it should be tested against random sparse graphs and standard SSM mixers for mixing quality, stability, and parameter/FLOP efficiency.