Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.
Here are a few tips on how to get started using Sage to work with posets, lattices and boolean algebras. These topics are introduced in chapters 6 and 13 of Applied Discrete Structures.
Most of the calculations in this notebook are based on the posets package containing the definitions in posets.py and poset_examples.py. They are part of the larger combinatorics package, combinat. More complete documentation: http://www.sagemath.org/doc/reference/combinat/posets.html
Here is one of several ways you can define a poset. It is essentially a digraph, but without any cycles which would violate the antisymmetry property of a poset.
The addition of an edge from 3 to 0 creates a cycle and the error message is very clear on this.
In addition to specifying a poset by its edge lists as above, there are several built-in posets, the PentagonPoset being among the simplest.
If a poset has unique minimal and maximal elements, and each pair of elements has a greatest lower bound (the meet) and least upper bound (the join) then we can consider whether elements have complements. These conditions are met for the pentagon poset.
Each element of the pentagon poset does indeed have a complement. In fact, 1's complement is not unique, but only one of the complements is given here.
A simple example where complements do not exist for all elements is the total ordering of set of integers 0, 1, 2, and 3. This is a predefined poset called ChainPoset(4). The middle elements, 1 and 2 have no complement.
Here is a single random poset on {0, 1, 2, ... 7}.
Suppose you wanted a random poset that had maximal and minimal elements, and had greatest lower bounds and least upper bounds for each pair of elements in the set. Here is a bit of code that will give it to you. In generating posets, we set the probability of an edge being included to 0.5. Changing this would clearly have an effect on the distribution of results.
Here is the operation table for the greatest lower bound operation on the poset above.
You might notice immediately that the entries in the matrix don't always match the poset diagram. This is because the matrix entries are indices to the list of poset elements that you get from the list method:
We close with some further examples of built-in posets. The first is an ordering of the partitions of a number, 4 in this case, according to whether each partition is an refinement of the other. Here, refinement means taking a list of numbers that add up to 4 and replacing a number with two numbers that add to it. So 2,2 is refined to 2,1,1 by breaking one of the 2's into 1 and 1.
Here is the ordering diagram of a boolean algebra with $2^4$ elements.
If you want to save a copy of this graph to your computer, you can't use show()because of the way it produces the image above. Use plot()instead and then save(filename). When you evaluate this cell, a link to the image file will appear.
Why this is a diamond poset should be clear:
For those who are unfamiliar with the weak ordering on permutations, see the discrete math wiki page. For basic information on permutations, see Section 15.3 of Applied Discrete Structures.