ALGORITHMS FOR LABELING CONSTANT WEIGHT GRAY CODES

LEVI, INESSA ; McFADDEN, ROBERT B. ; SEIF, STEVE

Glasgow mathematical journal, Tome 47 (2005) no. 2, pp. 221-236

Résumé

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.

Détail

DOI : 10.1017/S0017089505002430

Mots-clés : 94B25, 05A18, 20M20