Long non-transitive cycles of dice, II: exact circumferences and the growth rate
Let Gn be the digraph whose vertices are the C(2n−1, n) dice with n faces taking values in [n], with an arc X → Y when X beats Y in exactly ⌊n2/2⌋ + 1 of the n2 pairs of faces, and let L(n) be the length of a longest directed cycle of Gn. It was shown in part I that for n ≥ 7 the graph Gn has cycles of every length from 3 to (15n − 67)/2, that liminf (1/n) log2 L(n) ≥ 1/4 and that 797 ≤ L(7) ≤ 1029, and it was asked to determine L(7). We prove L(7) = 797, L(8) = 3482, L(9) = 18 893, L(10) = 77 403, L(11) = 319 115. In each case the circumference equals the largest number of dice that can be covered by vertex-disjoint cycles. The upper bounds are certified by integral solutions of the dual of the assignment linear program, and the lower bounds by explicit cycles. We then show that L(n) ≥ 1261176⌊(n−7)/12⌋ for n ≥ 31, hence liminf (1/n) log2 L(n) ≥ (log2 1261176)/12 > 1.688, compared with the trivial upper bound 2. The proof stacks neutral blocks (dice with a faces in [a] that beat each other in exactly half of the face pairs) on top of a short cycle, and uses a phase-shifted product. The data suggest that L(n)/C(2n−1, n) → 1. The certificates (dual vectors, cycles and flagged cycles), the independent verifiers, the search programs and the LaTeX source are in supplementary.zip (see anc/README.txt there).
Authors
- Vadim Genkin (ORCID: https://orcid.org/0009-0006-6354-3821)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24413310
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint