Sharedsage_worksheets / ADS2_Posets_Lattices.sagewsOpen in CoCalc
Worksheets related to Applied Discrete Structures
%html
<h1 style="font-size: 2em;">An Introduction to Posets and Lattices using Sage&nbsp;</h1>
<p><strong><em><a title="Applied Discrete Structures" href=" http://faculty.uml.edu/klevasseur/ads2" target="_blank">Applied Discrete Structures</a>&nbsp;</em>by Alan Doerr &amp; Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - &nbsp;No Derivative Works 3.0 United States License.</strong></p>
<p>Here are a few tips on how to get started using Sage to work with posets, lattices and boolean algebras. &nbsp;These topics are introduced in chapters 6 and 13 of <em>Applied Discrete Structures</em>.</p>

<p>Most of the calculations in this notebook are based on the posets package containing the definitions in posets.py &nbsp;and poset_examples.py. &nbsp; They are part of the larger combinatorics package, combinat. &nbsp;More complete documentation: <a href="http://www.sagemath.org/doc/reference/combinat/posets.html" target="_blank">http://www.sagemath.org/doc/reference/combinat/posets.html</a></p>

<p>Here is one of several ways you can define a poset. &nbsp;It is essentially a digraph, but without any cycles which would violate the antisymmetry property of a poset.</p>

An Introduction to Posets and Lattices using Sage 

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.

example=Poset({0:[2],1:[2],2:[3],3:[]})
example.show()

The addition of an edge from 3 to 0 creates a cycle and the error message is very clear on this.

Poset({0:[2],1:[2],2:[3],3:[0]})
Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> File "/ext/sage/sage-8.2_1604/local/lib/python2.7/site-packages/sage/combinat/posets/posets.py", line 691, in Poset D = transitive_reduction_acyclic(D) File "sage/graphs/generic_graph_pyx.pyx", line 1461, in sage.graphs.generic_graph_pyx.transitive_reduction_acyclic (build/cythonized/sage/graphs/generic_graph_pyx.c:20528) raise ValueError("The graph is not directed acyclic") ValueError: The graph is not directed acyclic

In addition to specifying a poset by its edge lists as above, there are several built-in posets, the PendagonPoset being among the simplest.

p=Posets.PentagonPoset()
p
Finite lattice containing 5 elements
p.show(vertex_colors="orange")

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.

[p.has_bottom(),p.has_top(),p.is_meet_semilattice(),p.is_join_semilattice()]
[True, True, True, True]

Each element of the pentagon poset does indeed have a complement. In fact, 1's complement is not unique, but only one of the compements is given here.  

[p.list(),p.complements()]
[[0, 1, 2, 3, 4], [4, 3, 1, 1, 0]]

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.

Posets.ChainPoset(4).complements()
[3, None, None, 0]

Among the built-in posets is a function called RandomPoset.  Here is documentation:

Posets.RandomPoset?

File: /tmp/sage-mac-app/local/lib/python2.6/site-packages/sage/combinat/posets/poset_examples.py

Type: <type ‘instancemethod’>

Definition: Posets.RandomPoset(n, p)

Docstring:

Generate a random poset on n vertices according to a probability distribution p.

EXAMPLES:

sage: Posets.RandomPoset(17,.15)
Finite poset containing 17 elements
Posets.RandomPoset??

File: /tmp/sage-mac-app/local/lib/python2.6/site-packages/sage/combinat/posets/poset_examples.py

Source Code (starting at line 240):

def RandomPoset(self, n,p):
    """
    Generate a random poset on ``n`` vertices according to a
    probability distribution ``p``.

    EXAMPLES::

        sage: Posets.RandomPoset(17,.15)
        Finite poset containing 17 elements
    """
    p = float(p)
    D = DiGraph(loops=False,multiedges=False)
    D.add_vertices(range(n))
    for i in range(n):
        for j in range(n):
            if random.random() < p:
                D.add_edge(i,j)
                if not D.is_directed_acyclic():
                    D.delete_edge(i,j)
    return Poset(D,cover_relations=False)

Here is a single random poset on {0, 1, 2, ... 7}.

P=Posets.RandomPoset(8,0.4)
P.show(vertex_colors="orange")

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.

P=Posets.RandomPoset(8,0.4)
while not(P.is_join_semilattice() and P.is_meet_semilattice() and not(P.is_chain())):
    P=Posets.RandomPoset(8,0.5)
P.show(vertex_colors="orange")

Here is the operation table for the greatest lower bound operation on the poset above.

P.meet_matrix()
[0 0 0 0 0 0 0 0] [0 1 1 1 1 1 1 1] [0 1 2 2 2 2 2 2] [0 1 2 3 3 3 2 3] [0 1 2 3 4 4 2 4] [0 1 2 3 4 5 2 5] [0 1 2 2 2 2 6 6] [0 1 2 3 4 5 6 7]

You might notice immediately that the entries in the matrix don't always match the poset diagram.  This is because the matrix entries are indicees to the list of poset elements that you get from the list method:

P.list()
[0, 1, 2, 3, 7, 4, 6, 5]

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.

Posets.IntegerPartitions(4).show(vertex_colors="orange")

Here is the ordering diagram of a boolean algebra with 242^4  elements.

Posets.DivisorLattice(12).plot().save("d_12.svg")
Posets.BooleanLattice(4).show(vertex_colors="orange")
/projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/graph_plot.py:270: DeprecationWarning: Use of vertex_colors=<string> is deprecated, use vertex_color=<string> and/or vertex_colors=<dict>. See http://trac.sagemath.org/21048 for details. self.set_vertices()

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).

Posets.BooleanLattice(4).plot(vertex_colors="orange").save('boolean4.png')

Why this is a diamond poset should be clear:

Posets.DiamondPoset(9).show(vertex_color="orange")

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.

Posets.SymmetricGroupWeakOrderPoset(3).show(vertex_color="orange")
Posets.SymmetricGroupWeakOrderPoset(4).show(vertex_color="yellow")
def lower_bounds(p,j):
    return filter(lambda k:p.le(j,k),p.list())
Poset({0:[2],1:[2],2:[3],3:[]})
example.show()
Finite poset containing 4 elements


Poset of Subsets


S=Set([1,2,3])
S
{1, 2, 3}
A=S.subsets()
subset={}
for a in A:
    subset[a]=filter(lambda b:a.intersection(b)==a ,A)
subset
{{3}: [{3}, {1, 3}, {2, 3}, {1, 2, 3}], {1, 2}: [{1, 2}, {1, 2, 3}], {}: [{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}], {2, 3}: [{2, 3}, {1, 2, 3}], {1}: [{1}, {1, 2}, {1, 3}, {1, 2, 3}], {1, 3}: [{1, 3}, {1, 2, 3}], {1, 2, 3}: [{1, 2, 3}], {2}: [{2}, {1, 2}, {2, 3}, {1, 2, 3}]}
DiGraph(subset).plot()
subset={}
for a in A:
    subset[a]=filter(lambda b:a.intersection(b)==a and b!=a ,A)
subset
{{3}: [{1, 3}, {2, 3}, {1, 2, 3}], {1, 2}: [{1, 2, 3}], {}: [{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}], {2, 3}: [{1, 2, 3}], {1}: [{1, 2}, {1, 3}, {1, 2, 3}], {1, 3}: [{1, 2, 3}], {1, 2, 3}: [], {2}: [{1, 2}, {2, 3}, {1, 2, 3}]}
p=Poset(subset)
p.plot()
p.hasse_diagram().plot()