Constructive techniques for labeling constant weight Gray codes with applications to minimal generating sets of semigroups
type: Item
instance of: scholarly article
title: Constructive techniques for labeling constant weight Gray codes with applications to minimal generating sets of semigroups
zbMATH Open document ID: 1029.05006
DOI: 10.1016/S0021-8693(03)00277-1
author: Inessa Levi
author: Steve Seif
published in: Journal of Algebra
publication date: 2003-08-20T00:00:00Z
review text: Given a positive integer \(n\), let \(X_n\) be the set \(\{1,2,\dots, n\}\). A partition \(\pi\) of \(X_n\) is said to have weight \(r\) if \(\pi\) has \(r\) distinct classes. The partition \(\pi\) and an \(r\)-element set \(A\) are said to be orthogonal if every class of \(\pi\) contains exactly one element of \(A\). An orthogonally labeled list for \(n\) and \(r\) is a sequence \(({\mathcal A},\pi)= A_1\), \(\pi_1\), \(A_2,\pi_2,\dots, A_{{n\choose r}}, \pi_{{n\choose r}}\) alternating between distinct \(r\)-sets \(A_i\) and distinct partitions \(\pi_i\) of weight \(r\), such that for \(i= 1,\dots,{n\choose r}- 1\), \(\pi_i\) is simultaneously orthogonal to \(A_i\) and \(A_{i+1}\), and \(\pi_{{n\choose r}}\) is simultaneously orthogonal to \(A_{{n\choose r}}\) and \(A_1\). A partition of the set \(X_n\) has type \[ \tau= d^{\mu(d_1)}_1 d^{\mu(d_2)}_2\cdots d^{\mu(d_k)}_k \] and weight \(r\) if it has \(\mu(d_i)\) classes of size \(d_i\), where \(d_1> d_2>\cdots> d_k\), \[ n= \sum^k_{i=1} d_i\mu(d_i)\quad\text{and}\quad r= \sum^k_{i=1}\mu(d_i). \] The partition type \(\tau\) is said to be exceptional if the number of distinct partitions of type \(\tau\) is less than \({n\choose r}\). Let \(G_{n,r}\) be the graph whose vertices are all the \(r\)-sets of \(X_n\), with two \(r\)-sets being adjacent if their intersection has exactly \(r-1\) elements. An orthogonally \(\tau\)-labeled list \(({\mathcal A},\pi)\) for which the set sequence \({\mathcal A}\) is a Hamiltonian cycle in \(G_{n,r}\) is called an orthogonally \(\tau\)-labeled Hamiltonian cycle. The Hamiltonian cycles of \(G_{n,r}\) are also called constant weight Gray codes. The partition type conjecture states that there exist orthogonally \(\tau\)-labeled Hamiltonian cycles for every non-exceptional partition type \(\tau\). This paper is mainly devoted to the proof of the partition type conjecture for a class of constant weight Gray codes. These results are applied in the theory of finite semigroups. The autho…
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 20M20
zbMATH DE Number: 1967908
zbMATH Keywords: partition
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: transformation
zbMATH Keywords: middle levels conjecture
zbMATH Keywords: idempotent rank of a semigroup
reviewed by: Ljuben Mutafchiev
MaRDI profile type: Publication
cites work: Q3741626
cites work: Two Hamilton cycles in bipartite reflective Kneser graphs
cites work: Idempotent generators in finite full transformation semigroups
cites work: Idempotent rank in finite full transformation semigroups
cites work: Q4552162
cites work: Sn-normal semigroups
cites work: ALGORITHMS FOR LABELING CONSTANT WEIGHT GRAY CODES
cites work: Q5463463
cites work: COMBINATORIAL TECHNIQUES FOR DETERMINING RANK AND IDEMPOTENT RANK OF CERTAIN FINITE SEMIGROUPS
cites work: Counting techniques to label constant weight Gray codes with links to minimal generating sets of semigroups
cites work: On idempotent ranks of semigroups of partial transformations.
cites work: Determinants of partition matrices
cites work: Q4144192
cites work: Monotone Gray codes and the middle levels problem
cites work: A mechanical counting method and combinatorial applications
cites work: Index system and separability of constant weight Gray codes
description: scientific article; zbMATH DE number 1967908