VibeMathed reports this item as partial. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.
Precise statement
Let $\Sigma$ be a finite nonempty alphabet of size $q$ with a fixed-point-free involution $a\mapsto\bar a$, and let $k\ge2$. The directed de Bruijn graph $B(q,k)$ has length-$k$ words as vertices and one-symbol-shift edges, including loops. Put $\rho(a_1\cdots a_k)=\bar a_k\cdots\bar a_1$.
What is the minimum cardinality $\tau_{\rm RC}(q,k)$ of a set $M\subseteq\Sigma^k$ such that $\rho(M)=M$ and deleting $M$ makes $B(q,k)$ acyclic?
This is the minimum-size symmetric-decycling problem described as open by Marçais, Elder and Kingsford (2024), Section 6. Section 5.1 also identifies the lack of constructions of symmetric ordinary minimum decycling sets. The classical minimum without symmetry is $N_q(k)=\frac1k\sum_{d\mid k}\varphi(d)q^{k/d}$. This entry reports a parity theorem toward the symmetry-constrained problem.
The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement
fidelity, correctness, priority, or novelty.
What AI did
GPT-5.6 Sol; GPT-5 Pro
The author reports using GPT-5.6 Sol and GPT-5 Pro through ChatGPT. The manuscript and public authorship disclosure describe substantial AI assistance with candidate proof arguments, symbolic identities, construction and verification code, adversarial checks and exposition. The author selected the research problem, directed the work and is responsible for the claims and final manuscript. The model names are author-supplied; the public disclosure does not identify model versions or assign individual lemmas to models. AI-assisted reflects the documented material assistance without asserting that AI discovered the central proof. Agreement between distinct implementations and author-side AI reviews is not independent specialist verification.
The posed question was read at source. Marcais, Elder and Kingsford, "k-nonical space: sketching with reverse complements", Bioinformatics 40(11), Section 6: "Being a symmetric decycling set is a strong condition that is still not well understood theoretically (e.g. the minimum size of a symmetric decycling set is unknown)." That is the quantity this paper bounds, and the submitter's quotation of it is accurate.
The mathematics was not checked here. The public 15-page manuscript carries analytical proofs, LaTeX source and an exact binary replay using only the standard library; the author's audit of 12 September records an anonymous clone matching all 50 reviewed files and a finite panel over binary $k=2,4,6,8,10,12$ with 612 legal firings and 14 mutations rejected. A finite panel does not establish the uniform $q$-ary theorem, and no independent specialist endorsement or formal proof is supplied. Partial because the question is answered for half its cases: every even order is settled exactly, and odd orders get a lower bound rather than the optimum.
GitHub manuscript: A Parity Theorem for Reverse-Complement-Invariant Minimum Decycling Sets in q-ary de Bruijn Graphs
Theorem 1.1 claims, for every finite nonempty alphabet with a fixed-point-free complement and every $k\ge2$,
$$
\tau_{\rm RC}(q,k)=N_q(k)\quad\Longleftrightarrow\quad k\text{ is even}.
$$
For odd $k\ge3$, Theorem 3.1 gives $\tau_{\rm RC}(q,k)\ge N_q(k)+q$, hence an excess of at least two for binary words and four for DNA. For even orders, Sections 6-8 provide a weighted construction and a direct spectral selector; integer weights permit exact polynomial-bit membership testing for a single word. The case $k=2$ is handled separately.
This completely classifies attainability of the ordinary minimum and partially answers the external symmetric-minimum question. It does not determine the general exact odd optimum, prove a packing-covering equality, give quantitative residual-path/window bounds, or establish biological performance. The classical ordinary minimum itself is prior work.
Known method families
argument (source-reported)
Source-reported tools: argument.
Independent: unknown · difference confidence: 0
What remains uncertain
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.
VibeMath has not independently verified the mathematical claim.
AI-attempt independence and training-data exposure are unknown unless explicitly documented.
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.