Partitioning Boolean lattices into chains of subsets (Q1094437)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partitioning Boolean lattices into chains of subsets |
scientific article |
Statements
Partitioning Boolean lattices into chains of subsets (English)
0 references
1987
0 references
The authors prove that the Boolean algebra \(B_ n\) of all subsets of an n element set can be partitioned into \(2^{n-2}\) chains of length four if and only if \(n\geq 9\). If \(n\leq 8\), then there are more than \(2^{n- 2}\) sets of cardinality [n/2] in \(B_ n\), so that the condition \(n\geq 9\) is clearly necessary. By induction, it suffices to prove that \(B_ 9\) admits a partition into four element chains. This is done, using Hall's theorem and the Kruskal-Katona theorem.
0 references
Boolean algebra
0 references
partition into four element chains
0 references