Sperner Properties of the Ideals of a Boolean Lattice
- Author(s): McHard, Richard W.
- Advisor(s): Harper, Lawrence H
- et al.
The Boolean lattice has many applications in computer science. The subsets of a Boolean lattice that are closed downward under the ordering relation are called ideals, and their study has a rich history. Problems of combinatorial optimization that involve the ideals of a Boolean lattice include combinational circuit design, bandwidth and wire length.
A graded poset P is such that every element has an unambiguous rank, or distance from the minimal element(s) of P in its Hasse diagram. The k-Sperner number of a graded poset P is the size of the largest subset of P with no more than k members that form a linear-ordered chain under the order relation of P. The k-Sperner number is a fundamental parameter of P in applications. It is easy to find if P is strongly Sperner; i.e., if, for any k, the k-Sperner number is the sum of the number of members of the k ranks that are largest in cardinality.
This is an algorithmic study of the Sperner properties of the ideals I(B) of a Boolean lattice B, which form a new lattice under set inclusion. I(B) is shown to be strongly Sperner if B has at most 6 generators. To do this, a new algorithm, the ideal exchange algorithm, was developed, proved correct, and used in conjunction with a flow algorithm to show that I(B) has a normal flow and is therefore strongly Sperner for the cases studied. This problem is computationally intensive (a double exponential in the number of generators) and was solved by breaking it into subcases that were run in parallel on the computer system at the University of California in Riverside.