ALGORITHMS FOR LABELING CONSTANT WEIGHT GRAY CODES
Inessa Levi, R. McFadden, Steve Seif · Glasgow Mathematical Journal · 2005
Let $n$ and $r$ be positive integers with $1\,{<}\,r\,{<}\,n$ , and let $X_n\,{=}\break\{1,2,\ldots,n\}$ . An $r$ -set $A$ and a partition $\pi$ of $X_n$ are said to be orthogonal if every class of $\pi$ meets $A$ in exactly one element. We prove that if $A_{1},A_{2},\ldots, A_{\binom n r}$ is a list of the distinct $r$ -sets of $X_ n$ with $|A_{i}\cap A_{i+1}|\,{=}\,r-1$ for $i=1,2,\ldots, \binom n r$ taken modulo $\binom n r$ , then there exists a list of distinct partitions $\pi_{1},\pi_{2},\ldots, \pi_{\binom n r}$ such that $\pi_{i}$ is orthogonal to both $A_{i}$ and $A_{i+1}$ . This result states that any constant weight Gray code admits a labeling by distinct orthogonal partitions. Using an algorithm from the literature on Gray codes, we provide a surprisingly efficient algorithm that on input $(n,r)$ outputs an orthogonally labeled constant weight Gray code. We also prove a two-fold Gray enumeration result, presenting an orthogonally labeled constant weight Gray code in which the partition labels form a cycle in the covering graph of the lattice of all partitions of $X_n$ . This leads to a conjecture related to the Middle Levels Conjecture. Finally, we provide an application of our results to calculating minimal generating sets of idempotents for finite semigroups.