Counting techniques to label constant weight Gray codes with links to minimal generating sets of semigroups

✍ Scribed by Inessa Levi; Steve Seif

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 173 KB
• Volume: 266
• Category: Article
• ISSN: 0021-8693
• DOI: 10.1016/s0021-8693(03)00276-x

✦ Synopsis

Let τ be a partition of the positive integer n. A partition of the set X n = {1, 2, . . . , n} is said to be of type τ if the sizes of its classes form the partition τ of n. Given 1 < r < n, an r element subset A of X n and a partition π of X n are said to be orthogonal if every class of π meets A in exactly one element. Let G n,r be the graph whose vertices are the r-element subsets of X n , with two sets being adjacent if they intersect in r -1 elements. The graph G n,r is Hamiltonian; Hamiltonian cycles of G n,r are early examples of error-correcting codes, where they came to be known as constant weight Gray codes. A Hamiltonian cycle A 1 , A 2 , . . . , A ( n r ) in G n,r is said to be orthogonally τ -labeled if there exists a list of distinct partitions π 1 , π 2 , . . . , π ( n r ) of type τ such that π i is orthogonal to both A i and A i+1 where i = 1, 2, . . . , n r taken modulo n r . For all but a finite class of partition types τ we present counting arguments to prove that any Hamiltonian cycle in G n,r can be orthogonally τ -labeled. The remaining cases, with the exception of cases which are equivalent to the celebrated Middle Levels Conjecture, are treated via constructive arguments in a sequel. A semigroup of transformations of X n is S n -normal if it is closed under conjugation by the permutations of X n . The combinatorics results here and in the sequel lead to a determination of the rank and idempotent rank of all S n -normal semigroups, thereby broadly generalizing the known result that the rank and idempotent rank of K(n, r) is S(n, r), a Stirling number of the second kind.