Order-matchings in the partition lattice (Q1903013)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Order-matchings in the partition lattice |
scientific article |
Statements
Order-matchings in the partition lattice (English)
0 references
5 June 1996
0 references
Denote \(\Pi_n\) the partition lattice of a finite \(n\)-element set ordered by refinement. A chain \(x_1,\dots, x_h\) in \(\Pi_n\) is said to be an upper chain if \(x_{i+ 1}\) covers \(x_i\) and \(\text{rank}(x_1)+ \text{rank}(x_h)\geq n\). This paper constructs inductively an upper chain decomposition for \(\Pi_n\). This provides a new proof of the result of Kung that there exists an order-matching from level of \(\text{rank}(k)\) into level of \(\text{rank}(k+ 1)\) in \(\Pi_n\) for \(k\leq n/2\). The proof is an extension of a method of de Bruijn, Tengbergen and Kruyswijk.
0 references
partition lattice
0 references
upper chain decomposition
0 references
order-matching
0 references