Zero-Sum Cycles in Regular Digraphs

Abstract

Let $Γ$ be a finite group of order $k\ge2$, and label the edges of a simple loopless $d$-regular digraph $D$ by elements of $Γ$. A directed cycle is zero-sum if the ordered product of its labels is the identity of $Γ$. We prove that a zero-sum cycle exists whenever $d\ge e^3(k-1)$. We also prove that every labelled $d$-regular digraph contains $Ω(d/k)$ pairwise vertex-disjoint zero-sum cycles. When $d\ge50k$, it contains $Ω(d^2/k)$ pairwise edge-disjoint zero-sum cycles. All three results are asymptotically optimal. The existence and packing results extend to Eulerian digraphs whose minimum and maximum common degrees $δ$ and $Δ$ satisfy $δ^3/Δ^2=Ω(k)$. The techniques extend a determinant--permanent argument of Friedland for even directed cycles.

Disclosure

“a logarithmic factor, rather than |Γ| = pd [29, 13]. It would be interesting to obtain analogous existence and packing bounds here in terms of the exponent. Acknowledgements We thank Noga Alon for helpful discussions. The author used ChatGPT 5.6 Pro for the devel- opment of the proof. The author independently verified all arguments and references and takes full responsibility for the paper.”

PDF page 20

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:16:30.130601Z

Structural counts