Constructive techniques for labeling constant weight Gray codes with applications to minimal generating sets of semigroups (Q1403877): Difference between revisions

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 authors establish simple formulas for ranks and idempotent ranks of semigroups which are closed under conjugation by the permutations of \(X_n\).