Partitioning Boolean lattices into chains of subsets

MaRDI QIDQ1094437zbMATH OpenFDO

Authors J. Griggs, Roger K. Yeh, Charles M. Grinstead

Publication date 1987

Published in Order (Search for Journal in Brave)

zbMATH Keywords

Boolean algebrapartition into four element chains

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Partial orders, general (06A06) Structure theory of Boolean algebras (06E05)

Review text

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.

Recommendations

• Partitioning Boolean lattices into antichains
• Partitioning the Boolean lattice into chains of large minimum size
• Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size
• scientific article; zbMATH DE number 1934409
• Partitions of large Boolean lattices
• Partitions of a finite Boolean lattice into intervals
• Partitioning the Boolean lattice into copies of a poset
• Improved bounds on the partitioning of the Boolean lattice into chains of equal size.
• scientific article; zbMATH DE number 3557853
• Proof of a conjecture on partitions of a Boolean lattice

Cited in

(16)

• Methods for nesting rank 3 normalized matching rank-unimodal posets
• Problems on chain partitions
• Proof of a conjecture on partitions of a Boolean lattice
• Chain partitions of products of two chains
• Partitions of large Boolean lattices
• Venn diagrams and symmetric chain decompositions in the Boolean lattice
• Partitioning the Boolean lattice into chains of large minimum size
• Partitioning the Boolean lattice into copies of a poset
• Reaping numbers and operations on Boolean algebras
• Decompositions of the Boolean lattice into rank-symmetric chains.
• scientific article; zbMATH DE number 427816 (Why is no real title available?)
• scientific article; zbMATH DE number 1934409 (Why is no real title available?)
• Improved bounds on the partitioning of the Boolean lattice into chains of equal size.
• On Collections of Subsets Containing No 4-Member Boolean Algebra
• Four-element generating sets of partition lattices and their direct products
• Footnote to a paper of Griggs, Yeh and Grinstead on partitioning into 4- chains

This page was built for publication: Partitioning Boolean lattices into chains of subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094437)