Explicit semisymmetric chain decomposition of the partition lattice (Q1567679): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q187114 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Sergei L. Bezrukov / rank | |||
Normal rank |
Revision as of 14:59, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Explicit semisymmetric chain decomposition of the partition lattice |
scientific article |
Statements
Explicit semisymmetric chain decomposition of the partition lattice (English)
0 references
29 January 2001
0 references
Let \(P\) be a ranked graded poset of rank \(n\). We say that the elements \(x_1,x_2,\dots,x_h\) form a symmetric chain if \(x_{i+1}\) covers \(x_i\) for \(i=1,\dots,h-1\) and \(\text{rank}(x_1)+\text{ rank}(x_h)=n\). If \(\text{ rank}(x_1)+\text{ rank}(x_h)\geq n\) the chain is called semisymmetric. It is known that there exists no symmetric chain decomposition of the partition lattice, because its existence would imply this poset is Sperner, which is not true. On the other hand a semisymmetric chain decomposition of this lattice is known. The main result of the paper is one more explicit construction for a symmetric chain decomposition of the partition lattice. It is shown that this new partition is not isomorphic to the known ones. The new method is based on a parenthesization procedure. A similar idea was used by Green and Kleitman to construct a symmetric chain decomposition of the Boolean lattice.
0 references
order-matching
0 references
set partitions
0 references
symmetric chain decomposition
0 references