HEXAGONbeta

A Parity Theorem for Reverse-Complement-Invariant Minimum Decycling Sets in q-ary de Bruijn Graphs

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Oleksiy Babanskyy ↗

Version 1 / Nov 10, 2026 / CC BY 4.0

Abstract

Let A\mathcal{A} be a finite alphabet with a fixed-point-free involutive complement, and let reverse complement act on the directed de Bruijn graph B(q,k)B(q,k) by reversing a word and complementing every letter. We prove that a reverse-complement-invariant ordinary minimum decycling set exists if and only if kk is even, for every integer k≥2k\geq2. This simultaneously covers the binary alphabet and the DNA alphabet with A↔TA\leftrightarrow T and C↔GC\leftrightarrow G. For odd kk, a primitive rotation cycle joins two reverse-complement-fixed lower states in opposite directions. Disjoint complementary alphabet pairs force at least qq deletions beyond the ordinary minimum. For even kk, choose injective antisymmetric real weights on the alphabet and form a weighted cyclotomic selector. We prove that arbitrary representatives on its zero-embedding rotation cycles preserve acyclicity, resolve those ties equivariantly, and establish the exact defect identity 1RC⁡(M)−1M=∇χ. \mathbf{1}_{\operatorname{RC}(M)}-\mathbf{1}_M=\nabla\chi . A finite sequence of legal full-alphabet source firings removes this nonnegative symmetric defect two coordinates at a time. We also identify a self-dual spectral ideal that gives a deterministic direct selector, rather than a simulated firing path. For integer weights, membership is decidable with polynomial bit complexity. The executable finite panel in the repository checks the binary specialization only; it is convention-level assurance and is not used in the all-order proof.

Author comments: 15 pages. Companion code and exact binary checks: https://github.com/aconsciousfractal/FCIG-RC-Invariant-Minimum-Decycling-Sets

Provenance statement

The author selected the problem, directed the research and retained responsibility for the mathematical claims, source attributions and publication decisions. The author reports using GPT-5.6 Sol and GPT-5 Pro via ChatGPT. These model names reproduce the author-reported disclosure in the prior aiXiv deposit; the manuscript does not identify model versions. AI assistants contributed substantively to candidate proof arguments, symbolic identities, construction and verification code, adversarial checks, manuscript drafting and revision. Individual proof steps are not attributed to particular models. The manuscript proves a parity classification for finite nonempty alphabets with a fixed-point-free involutive complement and word length k at least two. It determines the symmetric minimum at even orders. For odd orders at least three, the lower bound is the ordinary minimum plus the alphabet size; the exact general odd-order optimum remains open. No optimal longest remaining path or biological performance claim is made. The companion supplies distinct exact implementations and finite checks for the binary cases k=2,4,6,8,10,12. These support convention and implementation checks; they are not a proof of the all-order q-ary theorem. AI-assisted adversarial reviews are internal checks, not human peer review. For this submission, the author reports that no part of the contribution has been checked and understood by a human. No end-to-end formal verification is supplied. The same manuscript is available as aiXiv 2609.03273 v1: https://aixiv.online/abs/2609.03273v1 Source, companion checks, reproduction instructions and claim boundaries: https://github.com/aconsciousfractal/FCIG-RC-Invariant-Minimum-Decycling-Sets/tree/1f1b7156d3d8d5c326303427f97991212e9bb86a

Tools used

OpenAI
ChatGPTVersion GPT-5.6 Sol; GPT-5 Pro
Python Software Foundation
Python

References

  1. Champarnaud, Jean-Marc; Hansel, Georges; Perrin, Dominique. Unavoidable Sets of Constant Length. International Journal of Algebra and Computation, vol. 14, no. 2, pp. 241–251. 2004. https://doi.org/10.1142/S0218196704001700DOI
  2. Emiris, Ioannis Z.; Tsigaridas, Elias P. Computations with One and Two Real Algebraic Numbers. 2005. https://arxiv.org/abs/cs/0512072arXiv
  3. Marçais, Guillaume; DeBlasio, Dan; Kingsford, Carl. Sketching Methods with Small Window Guarantee Using Minimum Decycling Sets. Journal of Computational Biology, vol. 31, no. 7, pp. 597–615. 2024. https://doi.org/10.1089/cmb.2024.0544DOI
  4. Marçais, Guillaume; Elder, C. S.; Kingsford, Carl. k-nonical Space: Sketching with Reverse Complements. Bioinformatics, vol. 40, no. 11, pp. btae629. 2024. https://doi.org/10.1093/bioinformatics/btae629DOI
  5. Mykkeltveit, Johannes. A Proof of Golomb's Conjecture for the de Bruijn Graph. Journal of Combinatorial Theory, Series B, vol. 13, no. 1, pp. 40–45. 1972. https://doi.org/10.1016/0095-8956(72)90006-8DOI
  6. Pellow, David; Pu, Lianrong; Ekim, Bariş; Kotlar, Lior; Berger, Bonnie; Shamir, Ron; Orenstein, Yaron. Efficient Minimizer Orders for Large Values of k Using Minimum Decycling Sets. Genome Research, vol. 33, no. 7, pp. 1154–1161. 2023. https://doi.org/10.1101/gr.277644.123DOI
  7. Watkins, William; Zeitlin, Joel. The Minimal Polynomial of cos⁡(2π/n)\cos(2\pi/n). The American Mathematical Monthly, vol. 100, no. 5, pp. 471–474. 1993. https://doi.org/10.1080/00029890.1993.11990434DOI

Version history

  1. v1 · 15 pagesSubmitted by Oleksiy Babanskyy15 pages. Companion code and exact binary checks: https://github.com/aconsciousfractal/FCIG-RC-Invariant-Minimum-Decycling-SetsCurrentNov 09, 2026