On the existence of symmetric chain decompositions in a quotient of the Boolean lattice (Q1044888)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the existence of symmetric chain decompositions in a quotient of the Boolean lattice
scientific article

    Statements

    On the existence of symmetric chain decompositions in a quotient of the Boolean lattice (English)
    0 references
    0 references
    0 references
    15 December 2009
    0 references
    The paper under review is not in the strict sense of the word a mathematical research paper. The style of it is merely expository and avoids the precise mathematical formalism. The paper is a short report about a mathematical result concerning finite Boolean lattices, which originally appeared in [\textit{J. Griggs, C. E. Killian} and \textit{C. D. Savage}, Electron. J. Comb. 11, No. 1, Research paper R2, 30 p. (2004; Zbl 1034.06001)] under the title ``Venn diagrams and symmetric chain decompositions in the Boolean lattice''. Here are some definitions and results: Let \(B_n\) be the collection of all subsets of \(\{1,2,\cdots,n\}\), ordered by inclusion. \(B_n\) is a Boolean lattice having \(2^n\) elements. Let be \(S\in B_n\). \(S\) can be viewed as an \(n\)-bit string \(x_1\cdots x_n\) whose \(i\)th bit \(x_i=1\) iff \(i\in S\) (otherwise \(x_i=0\)). The cardinality of \(S\) (notation: \(|S|\)) is the number of \(x_i=1\) in the corresponding string. Moreover, a \textit{chain} in \(B_n\) is a sequence \(S_1\subseteq \cdots \subseteq S_k\). Only chains satisfying \(|S_i|= |S_{i-1}|+1\) for all \(i\geq 2\) will be of interest. The chain is \textit{symmetric} if \(k+1=n.\) A key concept is a \textit{symmetric chain decomposition} (SCD) of \(B_n\), which means a partition of \(B_n\) such that all symmetric chains are classes of the partition. The first question is: Has every \(B_n\) an SCD? Yes, \(B_n\) has an SCD for every \(n\), and there exists an algorithm to get it. There is a modification of the above question. Let \(\Theta\) be an equivalence on \(B_n\) Choose a representative from every partition class \([S]\Theta\) and form a subposet \(R_n\) of \(B_n.\) Has \(R_n\) now an SCD? The authors report about the equivalence \(\Delta\) generated by the cyclic rotation \(\sigma\): Let \(x=x_1\cdots x_n\in B_n\). Then \(\sigma(x)=x_2 x_3\cdots x_n x_1\). Define \(x\Delta y\) iff \(y=\sigma^i(x)\) for some \(i\). Now the result is: Let \(n\) be a prime number. Then there exists a poset \(R_n\) of representatives having an SCD.
    0 references
    0 references
    symmetric chain
    0 references
    decomposition
    0 references
    necklace
    0 references
    quotient of Boolean lattice
    0 references
    0 references