\(\mathit{SB}(3,n)\) has no Hamiltonian cycle when \(n\) is even: a sign-of-permutation proof, with extension to all odd \(m\equiv 3\pmod 4\)

Discrete MathematicsarXiv:2605.09489PDF

Publish this paper in The AIPR Journal

Are you an author? Turn this AI review into a permanent, citable journal entry with a cover, open comments, and Scholar metadata.

Not the corresponding author? Request this paper

AIPR assessment

Problem difficulty is moderate to high within a focused combinatorics niche: the question is a specific open exercise, but it sits in an active area with a large background literature on de Bruijn-like constructions. The paper's strengths reinforce each other, because the proof is simple, structural, and complete, so the main theorem is easy to trust once the parity identities are accepted. The main weakness is scope, not correctness: the result is an impossibility theorem with no constructive c

Abstract

We resolve exercise 7.2.2.4--224 of Knuth's Pre-Fascicle 8a (10 April 2026 draft, rated [46]): the digraph $\mathit{SB}(3,n)$ has no Hamiltonian cycle when $n$ is even. The argument is a sign-of-permutation obstruction. Writing the successor map of a candidate Hamiltonian cycle as $f_S = A_b \circ σ$, $\operatorname{sgn}(A_b)=+1$ when $m$ is odd, so $\operatorname{sgn}(f_S)=\operatorname{sgn}(σ)$ for every choice set $S$. A short dihedral Burnside computation shows $\operatorname{sgn}(σ)=-1$ on $Σ_3^n$ for even $n$, contradicting the sign $+1$ required of a single $3^n$-cycle. The same argument gives the stronger statement that $\mathit{SB}(m,n)$ has no Hamiltonian cycle whenever $m$ is odd with $m\equiv 3\pmod 4$ and $n$ is even; this restricts the residue classes in which Knuth's hint to Ex.~225 (existence of Hamiltonian cycles in $\mathit{SB}(m,n)$ for all $m>3$ and $n>2$) can hold.

Score Breakdown

Holistic Impression
79
Novelty
88
Rigor
94
Applicability
61
Clarity
88
Citation
74
Confidence: 85%

More from this week

More in Discrete Mathematics