|
|
|
|
partition lattice
|
(Definition)
|
|
|
The partition lattice (or lattice of partitions)  is the lattice of set partitions of the set
![$ [n]=\{1,\dots,n\}$](http://images.planetmath.org:8080/cache/objects/5581/l2h/img2.png "$ [n]=\{1,\dots,n\}$") . The partial order on  is defined by refinement, setting  if any only if each cell of  is contained in a cell of  .
If  , then  is a chain. But  is not even a distributive lattice:
Moreover, the lattice  is an interval in the lattice  , so the lattice of partitions on ![$ [n]$](http://images.planetmath.org:8080/cache/objects/5581/l2h/img13.png "$ [n]$") is distributive only if  . On the other hand, it is always a graded poset with rank function
 , where  is the number of cells in  .
Each partition of ![$ [n]$](http://images.planetmath.org:8080/cache/objects/5581/l2h/img18.png "$ [n]$") has a corresponding Young tableau. To determine the Young tableau corresponding to a partition, we arrange the cells of the partition in order of decreasing size, breaking ties by allowing cells with smaller minimal elements to come first. The shape of the tableau is determined by the
sizes of the cells, and the labels for the boxes come from the sets.
To illustrate the process of associating a partition with a tableau, we perform it for the partition
 of ![$ [9]$](http://images.planetmath.org:8080/cache/objects/5581/l2h/img20.png "$ [9]$") . There is one cell of size  , namely,  . There are two cells of size  ,  and  . To order them we compare their minimal elements. Since  , we list  before  . Similarly, we list  before  . After sorting we have rewritten the partition as
 . Thus our tableau will have shape
 . Labeling the shape gives us the following Young tableau.
- 1
- Stanley, R., Enumerative Combinatorics, vol. 1, 2nd ed., Cambridge University Press, Cambridge, 1996.
|
Anyone with an account can edit this entry. Please help improve it!
"partition lattice" is owned by mps.
|
|
(view preamble)
See Also: lattice
| Other names: |
lattice of partitions |
| Keywords: |
partition lattice, non-modular, non-distributive, graded |
|
|
Cross-references: labeling, labels, minimal elements, size, decreasing, order, Young tableau, partition, number, rank function, graded poset, distributive, interval, distributive lattice, chain, contained, refinement, partial order, lattice
There are 2 references to this entry.
This is version 6 of partition lattice, born on 2004-02-15, modified 2007-03-07.
Object id is 5581, canonical name is PartitionLattice.
Accessed 3279 times total.
Classification:
| AMS MSC: | 06B20 (Order, lattices, ordered algebraic structures :: Lattices :: Varieties of lattices) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & 123\ar@{-}[ld]\ar@{-}[d]\ar@{-... ... 1/23\ar@{-}[rd] & 12/3\ar@{-}[d] & 13/2\ar@{-}[ld] \ & 1/2/3 & } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/5581/l2h/img10.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & 123\ar@{-}[ld]\ar@{-}[d]\ar@{-... ... 1/23\ar@{-}[rd] & 12/3\ar@{-}[d] & 13/2\ar@{-}[ld] \ & 1/2/3 & } } \end{xy}$")
