$\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$
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909030221348864 |
|---|---|
| author | Li, Shisheng |
| author_facet | Li, Shisheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09489 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | $\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$ Li, Shisheng Combinatorics 05C45 (Primary), 05A05, 20B30, 94A55 (Secondary) 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. |
| title | $\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$ |
| topic | Combinatorics 05C45 (Primary), 05A05, 20B30, 94A55 (Secondary) |
| url | https://arxiv.org/abs/2605.09489 |