Inessa Levi

Document Type


Publication Date


Publication Title

Cambridge University Press


We prove that for positive integers n and r satisfying 1 < r < n, with the single exception of n = 4 and r = 2, there exists a constant weight Gray code of r-sets of Xn = {1,2,... ,n} that admits an orthogonal labelling by distinct partitions, with each subsequent partition obtained from the previous one by an application of a permutation of the underlying set. Specifically, an r-set A and a partition •K of Xn are said to be orthogonal if every class of n meets A in exactly one element. We prove that for all n and r as stated, and i = 1,2,..., I J taken modulo [ J, there exists a list Ai, A2,..., A(n\ of the distinct r-sets of Xn with \A\ n Aj+1| = r - 1 and a list of distinct partitions TTI, 7T2,..., irin\ such that TTJ is orthogonal to both Ai and Ai+i, and 7Tj+i = TTiAj for a suitable permutation A* of Xn.

Included in

Mathematics Commons