Zero-Star Prefix-Reversal Complements

Abstract

Deleting any retained b-edge from an independently defined zero star gives a Hamiltonian path with the exact complementary word Z_j.

A configuration is a permutation v of the positions Fin(m+1); v(i) is the label at position i. Right multiplication acts on positions: (v g)(i)=v(g(i)). The generators a, b and c reverse the first m+1, m and m-1 positions respectively. The oriented circle of v is its tuple modulo rotation. For a marked label t and an oriented residual circle W, Star(t,W) consists of all configurations whose deletion of t is W or its reverse. This domain is specified before any path is constructed. The factor retains every a-edge, the b-edge when t is not at the last position, and the c-edge when t is at the last position, within the actual Cayley graph generated by these three reversals.

Put R=ab and B=bc. R rotates the entire tuple left by one position; B rotates its first m positions left by one and fixes the last position. Choose a base z with t last. The coordinates (k,r,s) in Fin(m) times Fin(m+1) times Bool represent z B^k R^r when s is false and z B^k R^r a when s is true. For m at least three this is a bijection onto Star(t,W), where W is the residual circle of z. Deletion orientation distinguishes s, the position of t distinguishes r, and the rotation of the residual tuple distinguishes k. Exhaustiveness follows by rotating any configuration to put t last, and reversing its residual direction when needed. A residual circle on at least three distinct labels cannot equal its reverse, by preservation of untouched restrictions under circular deletion transport.

Write E(k,r) and O(k,r) for the false and true coordinates. The native order is E(k,0), O(k,0), E(k,1), O(k,1), through E(k,m), O(k,m). An a-edge joins E(k,r) to O(k,r), a b-edge joins O(k,r) to E(k,r+1) for r less than m, and a c-edge joins O(k,m) to E(k+1,0), with k read modulo m. Thus the literal circular word is (Hc)^m, where U_k=(ab)^k a and H=U_m. There are exactly 2m(m+1) configurations.

Theorem 1.1 (The Exact Hamiltonian Complement).

$$\forall m\in \mathrm{Nat},(6\le m)\Rightarrow (\forall t\in \mathrm{Fin}\left(m+1\right),\forall W\in \mathrm{Cycle}\left(\mathrm{Fin}\left(m+1\right)\right),\forall v\in \mathrm{Configuration}\left(m\right),\forall j\in \mathrm{Fin}\left(m\right),(\mathrm{Star}\left(t,W,v\right)\wedge \mathrm{apply}\left(v,\mathrm{castSucc}\left(j\right)\right)=t)\Rightarrow (\mathrm{Star}\left(t,W,\mathrm{rightMultiply}\left(v,\mathrm{b}\left(m\right)\right)\right)\wedge \left(\exists w\in \mathrm{Walk}\left(\mathrm{deleteEdges}\left(\mathrm{starFactor}\left(t,W\right),\mathrm{singletonEdge}\left(v,\mathrm{rightMultiply}\left(v,\mathrm{b}\left(m\right)\right)\right)\right),v,\mathrm{rightMultiply}\left(v,\mathrm{b}\left(m\right)\right)\right),\mathrm{IsHamiltonian}\left(w\right)\wedge \left(\mathrm{length}\left(w\right)=2\cdot m\cdot \left(m+1\right)-1\wedge \mathrm{map}\left(\mathrm{support}\left(w\right),\mathrm{underlyingConfiguration}\right)=\mathrm{scanl}\left(\mathrm{rightMultiply},v,\mathrm{zWord}\left(m,\mathrm{val}\left(j\right)\right)\right)\right)\right)))$$

Proof. Machine-checked in Lean as D5/S3/Combinatorics/Graph/PrefixReversalZeroStarComplement.zeroStar_b_complement_hamiltonian (✓ std3). ∎

Source. Repository-derived.

Commentary.

For every m at least six, every marked label t, every residual circle W, and every v in Star(t,W), suppose t occurs at position j with j in Fin(m). Then vb is also in Star(t,W). After deleting the undirected edge between v and vb from the induced factor, there is a Hamiltonian walk from v to vb of length 2m(m+1)-1. Its configuration support is exactly the successive right products starting at v of the literal word Z_j=U_j(cH)^(m-1)cU_(m-j-1); powers here mean repetition of lists, not replacement by a group product.

To handle either residual orientation uniformly, take z=v U_j. The word U_j is an involution, so v is O(0,j) relative to z, and t is last in z. Number the native coordinates by 2r+s+2(m+1)k. Start at the odd rank 2j+1 and traverse the remaining circle backwards. The rank sequence visits every coordinate once, ends at the successor of the cut rank, and no consecutive pair is the removed edge. All its consecutive pairs are retained native edges. Reversing the tail of the circle word rotated to the cut gives exactly Z_j. This establishes both full coverage of the independent domain and the literal support identity.

The result concerns one zero star and its retained factor. It does not connect distinct stars or assert a Hamiltonian cycle on all permutations.

References

• Truth anchor: D5/S3/Combinatorics/Graph/PrefixReversalZeroStarComplement.zeroStar_b_complement_hamiltonian
• Dependency: D5/S0/CayleyGrowth/PrefixReversalTripleOddNonGeneration
• Dependency: D5/S3/Combinatorics/CircularWords/CircularDeletionTransport