Finite semilattices and lattices

This module implements finite (semi)lattices. It defines:

FiniteJoinSemilattice A class for finite join semilattices.
FiniteMeetSemilattice A class for finite meet semilattices.
FiniteLatticePoset A class for finite lattices.
JoinSemilattice() Construct a join semi-lattice.
LatticePoset() Construct a lattice.
MeetSemilattice() Construct a meet semi-lattice.

List of (semi)lattice methods

complements() Return the list of complements of an element, or the dictionary of complements for all elements.
is_atomic() Return True if the lattice is atomic.
is_complemented() Return True if the lattice is complemented.
is_distributive() Return True if the lattice is distributive.
is_lower_semimodular() Return True if the lattice is lower semimodular.
is_modular() Return True if the lattice is lower modular.
is_modular_element() Return True if given element is modular in the lattice.
is_upper_semimodular() Return True if the lattice is upper semimodular.
is_supersolvable() Return True if the lattice is supersolvable.
join() Return the join of given elements in the join semi-lattice.
join_matrix() Return the matrix of joins of all elements of the join semi-lattice.
meet() Return the meet of given elements in the meet semi-lattice.
meet_matrix() Return the matrix of meets of all elements of the meet semi-lattice.
class sage.combinat.posets.lattices.FiniteJoinSemilattice(hasse_diagram, elements, category, facade, key)

Bases: sage.combinat.posets.posets.FinitePoset

We assume that the argument passed to FiniteJoinSemilattice is the poset of a join-semilattice (i.e. a poset with least upper bound for each pair of elements).

TESTS:

sage: J = JoinSemilattice([[1,2],[3],[3]])
sage: TestSuite(J).run()
sage: P = Poset([[1,2],[3],[3]])
sage: J = JoinSemilattice(P)
sage: TestSuite(J).run()
Element

alias of JoinSemilatticeElement

join(x, y=None)

Return the join of given elements in the lattice.

INPUT:

  • x, y - two elements of the (semi)lattice OR
  • x - a list or tuple of elements

EXAMPLES:

sage: D = Posets.DiamondPoset(5)
sage: D.join(1, 2)
4
sage: D.join(1, 1)
1
sage: D.join(1, 4)
4
sage: D.join(1, 0)
1

Using list of elements as an argument. Join of empty list is the bottom element:

sage: B4=Posets.BooleanLattice(4)
sage: B4.join([2,4,8])
14
sage: B4.join([])
0

Test that this method also works for facade lattices:

sage: L = LatticePoset([[1,2],[3],[3]], facade = True)
sage: L.join(1, 0)
1
sage: L.join(1, 2)
3
join_matrix()

Return a matrix whose (i,j) entry is k, where self.linear_extension()[k] is the join (least upper bound) of self.linear_extension()[i] and self.linear_extension()[j].

EXAMPLES:

sage: P = LatticePoset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False)
sage: J = P.join_matrix(); J
[0 1 2 3 4 5 6 7]
[1 1 3 3 7 7 7 7]
[2 3 2 3 4 6 6 7]
[3 3 3 3 7 7 7 7]
[4 7 4 7 4 7 7 7]
[5 7 6 7 7 5 6 7]
[6 7 6 7 7 6 6 7]
[7 7 7 7 7 7 7 7]
sage: J[P(4).vertex,P(3).vertex] == P(7).vertex
True
sage: J[P(5).vertex,P(2).vertex] == P(5).vertex
True
sage: J[P(5).vertex,P(2).vertex] == P(2).vertex
False
class sage.combinat.posets.lattices.FiniteLatticePoset(hasse_diagram, elements, category, facade, key)

Bases: sage.combinat.posets.lattices.FiniteMeetSemilattice, sage.combinat.posets.lattices.FiniteJoinSemilattice

We assume that the argument passed to FiniteLatticePoset is the poset of a lattice (i.e. a poset with greatest lower bound and least upper bound for each pair of elements).

TESTS:

sage: L = LatticePoset([[1,2],[3],[3]])
sage: TestSuite(L).run()
sage: P = Poset([[1,2],[3],[3]])
sage: L = LatticePoset(P)
sage: TestSuite(L).run()
Element

alias of LatticePosetElement

complements(element=None)

Return the list of complements of an element in the lattice, or the dictionary of complements for all elements.

Elements x and y are complements if their meet and join are respectively the bottom and the top element of the lattice.

INPUT:

  • element - an element of the poset whose complement is returned. If None (default) then dictionary of complements for all elements having at least one complement is returned.

EXAMPLES:

sage: L=LatticePoset({0:['a','b','c'], 'a':[1], 'b':[1], 'c':[1]})
sage: C = L.complements()

Let us check that 'a' and 'b' are complements of each other:

sage: 'a' in C['b']
True
sage: 'b' in C['a']
True

Full list of complements:

sage: L.complements() # random
{0: [1], 1: [0], 'a': ['b', 'c'], 'b': ['c', 'a'], 'c': ['b', 'a']}

sage: L=LatticePoset({0:[1,2],1:[3],2:[3],3:[4]})
sage: L.complements() # random
{0: [4], 4: [0]}
sage: L.complements(1)
[]

TESTS:

sage: L=LatticePoset({0:['a','b','c'], 'a':[1], 'b':[1], 'c':[1]})
sage: for v,v_complements in L.complements().items():
....:     for v_c in v_complements:
....:         assert L.meet(v,v_c) == L.bottom()
....:         assert L.join(v,v_c) == L.top()
is_atomic()

Returns True if self is an atomic lattice and False otherwise.

A lattice is atomic if every element can be written as a join of atoms.

EXAMPLES:

sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]})
sage: L.is_atomic()
True

sage: L = LatticePoset({0:[1,2],1:[3],2:[3],3:[4]})
sage: L.is_atomic()
False

NOTES:

See [Sta97], Section 3.3 for a discussion of atomic lattices.

REFERENCES:

[Sta97]Stanley, Richard. Enumerative Combinatorics, Vol. 1. Cambridge University Press, 1997
is_complemented()

Returns True if self is a complemented lattice, and False otherwise.

EXAMPLES:

sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]})
sage: L.is_complemented()
True

sage: L = LatticePoset({0:[1,2],1:[3],2:[3],3:[4]})
sage: L.is_complemented()
False
is_distributive()

Return True if the lattice is distributive, and False otherwise.

A lattice (L, \vee, \wedge) is distributive if meet distributes over join: x \wedge (y \vee z) = (x \wedge y)
\vee (x \wedge z) for every x,y,z \in L just like x \cdot
(y+z)=x \cdot y + x \cdot z in normal arithmetic. For duality in lattices it follows that then also join distributes over meet.

EXAMPLES:

sage: L = LatticePoset({0:[1,2],1:[3],2:[3]})
sage: L.is_distributive()
True
sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]})
sage: L.is_distributive()
False
is_lower_semimodular()

Return True if the lattice is lower semimodular and False otherwise.

A lattice is lower semimodular if for any x in the poset that covers y and z, both y and z cover their meet.

See also is_modular() and is_upper_semimodular().

See Wikipedia article Semimodular_lattice

EXAMPLES:

sage: L = posets.DiamondPoset(5)
sage: L.is_lower_semimodular()
True

sage: L = posets.PentagonPoset()
sage: L.is_lower_semimodular()
False

sage: L = posets.ChainPoset(6)
sage: L.is_lower_semimodular()
True

ALGORITHM:

Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1].

is_modular(L=None)

Return True if the lattice is modular and False otherwise.

Using the parameter L, this can also be used to check that some subset of elements are all modular.

INPUT:

  • L – (default: None) a list of elements to check being modular, if L is None, then this checks the entire lattice

An element x in a lattice L is modular if x \leq b implies

x \vee (a \wedge b) = (x \vee a) \wedge b

for every a, b \in L. We say L is modular if x is modular for all x \in L. There are other equivalent definitions, see Wikipedia article Modular_lattice.

EXAMPLES:

sage: L = posets.DiamondPoset(5)
sage: L.is_modular()
True

sage: L = posets.PentagonPoset()
sage: L.is_modular()
False

sage: L = posets.ChainPoset(6)
sage: L.is_modular()
True

sage: L = LatticePoset({1:[2,3],2:[4,5],3:[5,6],4:[7],5:[7],6:[7]})
sage: L.is_modular()
False
sage: [L.is_modular([x]) for x in L]
[True, True, False, True, True, False, True]

ALGORITHM:

Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1].

is_modular_element(x)

Return True if x is a modular element and False otherwise.

INPUT:

  • x – an element of the lattice

An element x in a lattice L is modular if x \leq b implies

x \vee (a \wedge b) = (x \vee a) \wedge b

for every a, b \in L.

See also

is_modular() to check modularity for the full lattice or some set of elements

EXAMPLES:

sage: L = LatticePoset({1:[2,3],2:[4,5],3:[5,6],4:[7],5:[7],6:[7]})
sage: L.is_modular()
False
sage: [L.is_modular_element(x) for x in L]
[True, True, False, True, True, False, True]
is_supersolvable()

Return True if self is a supersolvable lattice and False otherwise.

A lattice L is supersolvable if there exists a maximal chain C such that every x \in C is a modular element in L.

EXAMPLES:

sage: L = posets.DiamondPoset(5)
sage: L.is_supersolvable()
True

sage: L = posets.PentagonPoset()
sage: L.is_supersolvable()
False

sage: L = posets.ChainPoset(6)
sage: L.is_supersolvable()
True

sage: L = LatticePoset({1:[2,3],2:[4,5],3:[5,6],4:[7],5:[7],6:[7]})
sage: L.is_supersolvable()
True
sage: L.is_modular()
False

sage: L = LatticePoset({0: [1, 2, 3, 4], 1: [5, 6, 7],
....:                   2: [5, 8, 9], 3: [6, 8, 10], 4: [7, 9, 10],
....:                   5: [11], 6: [11], 7: [11], 8: [11],
....:                   9: [11], 10: [11]})
sage: L.is_supersolvable()
False
is_upper_semimodular()

Return True if the lattice is upper semimodular and False otherwise.

A lattice is upper semimodular if for any x in the poset that is covered by y and z, both y and z are covered by their join.

See also is_modular() and is_lower_semimodular().

See Wikipedia article Semimodular_lattice

EXAMPLES:

sage: L = posets.DiamondPoset(5)
sage: L.is_upper_semimodular()
True

sage: L = posets.PentagonPoset()
sage: L.is_upper_semimodular()
False

sage: L = posets.ChainPoset(6)
sage: L.is_upper_semimodular()
True

sage: L = LatticePoset(posets.IntegerPartitions(4))
sage: L.is_upper_semimodular()
True

ALGORITHM:

Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1].

sublattice(elms)

Return the smallest sublattice containing elements on the given list.

INPUT:

  • elms – a list of elements of the lattice.

EXAMPLES:

sage: L=LatticePoset(( [], [[1,2],[1,17],[1,8],[2,3],[2,22],[2,5],[2,7],[17,22],[17,13],[8,7],[8,13],[3,16],[3,9],[22,16],[22,18],[22,10],[5,18],[5,14],[7,9],[7,14],[7,10],[13,10],[16,6],[16,19],[9,19],[18,6],[18,33],[14,33],[10,19],[10,33],[6,4],[19,4],[33,4]] ))
sage: L.sublattice([14, 13, 22]).list()
[1, 2, 8, 7, 14, 17, 13, 22, 10, 33]

sage: L = Posets.BooleanLattice(3)
sage: L.sublattice([3,5,6,7])
Finite lattice containing 8 elements

Note

This is very unoptimal algorithm. Better one is described on “Computing the sublattice of a lattice generated by a set of elements” by K. Bertet and M. Morvan. Feel free to implement it.

class sage.combinat.posets.lattices.FiniteMeetSemilattice(hasse_diagram, elements, category, facade, key)

Bases: sage.combinat.posets.posets.FinitePoset

Note

We assume that the argument passed to MeetSemilattice is the poset of a meet-semilattice (i.e. a poset with greatest lower bound for each pair of elements).

TESTS:

sage: M = MeetSemilattice([[1,2],[3],[3]])
sage: TestSuite(M).run()
sage: P = Poset([[1,2],[3],[3]])
sage: M = MeetSemilattice(P)
sage: TestSuite(M).run()
Element

alias of MeetSemilatticeElement

meet(x, y=None)

Return the meet of given elements in the lattice.

EXAMPLES:

sage: D = Posets.DiamondPoset(5)
sage: D.meet(1, 2)
0
sage: D.meet(1, 1)
1
sage: D.meet(1, 0)
0
sage: D.meet(1, 4)
1

Using list of elements as an argument. Meet of empty list is the bottom element:

sage: B4=Posets.BooleanLattice(4)
sage: B4.meet([3,5,6])
0
sage: B4.meet([])
15

Test that this method also works for facade lattices:

sage: L = LatticePoset([[1,2],[3],[3]], facade = True)
sage: L.meet(2, 3)
2
sage: L.meet(1, 2)
0
meet_matrix()

Return a matrix whose (i,j) entry is k, where self.linear_extension()[k] is the meet (greatest lower bound) of self.linear_extension()[i] and self.linear_extension()[j].

EXAMPLES:

sage: P = LatticePoset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False)
sage: M = P.meet_matrix(); M
[0 0 0 0 0 0 0 0]
[0 1 0 1 0 0 0 1]
[0 0 2 2 2 0 2 2]
[0 1 2 3 2 0 2 3]
[0 0 2 2 4 0 2 4]
[0 0 0 0 0 5 5 5]
[0 0 2 2 2 5 6 6]
[0 1 2 3 4 5 6 7]
sage: M[P(4).vertex,P(3).vertex] == P(0).vertex
True
sage: M[P(5).vertex,P(2).vertex] == P(2).vertex
True
sage: M[P(5).vertex,P(2).vertex] == P(5).vertex
False
sage.combinat.posets.lattices.JoinSemilattice(data, *args, **options)

Construct a join semi-lattice from various forms of input data.

INPUT:

  • data, *args, **options – data and options that will be passed down to Poset() to construct a poset that is also a join semilattice.

EXAMPLES:

Using data that defines a poset:

sage: JoinSemilattice([[1,2],[3],[3]])
Finite join-semilattice containing 4 elements

sage: JoinSemilattice([[1,2],[3],[3]], cover_relations = True)
Finite join-semilattice containing 4 elements

Using a previously constructed poset:

sage: P = Poset([[1,2],[3],[3]])
sage: J = JoinSemilattice(P); J
Finite join-semilattice containing 4 elements
sage: type(J)
<class 'sage.combinat.posets.lattices.FiniteJoinSemilattice_with_category'>

If the data is not a lattice, then an error is raised:

sage: elms = [1,2,3,4,5,6,7]
sage: rels = [[1,2],[3,4],[4,5],[2,5]]
sage: JoinSemilattice((elms, rels))
Traceback (most recent call last):
...
ValueError: Not a join semilattice.
sage.combinat.posets.lattices.LatticePoset(data, *args, **options)

Construct a lattice from various forms of input data.

INPUT:

  • data, *args, **options – data and options that will be passed down to Poset() to construct a poset that is also a lattice.

OUTPUT:

FiniteLatticePoset – an instance of FiniteLatticePoset

See also

Posets, FiniteLatticePosets, JoinSemiLattice(), MeetSemiLattice()

EXAMPLES:

Using data that defines a poset:

sage: LatticePoset([[1,2],[3],[3]])
Finite lattice containing 4 elements

sage: LatticePoset([[1,2],[3],[3]], cover_relations = True)
Finite lattice containing 4 elements

Using a previously constructed poset:

sage: P = Poset([[1,2],[3],[3]])
sage: L = LatticePoset(P); L
Finite lattice containing 4 elements
sage: type(L)
<class 'sage.combinat.posets.lattices.FiniteLatticePoset_with_category'>

If the data is not a lattice, then an error is raised:

sage: elms = [1,2,3,4,5,6,7]
sage: rels = [[1,2],[3,4],[4,5],[2,5]]
sage: LatticePoset((elms, rels))
Traceback (most recent call last):
...
ValueError: Not a lattice.

Creating a facade lattice:

sage: L = LatticePoset([[1,2],[3],[3]], facade = True)
sage: L.category()
Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets
sage: parent(L[0])
Integer Ring
sage: TestSuite(L).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented
sage.combinat.posets.lattices.MeetSemilattice(data, *args, **options)

Construct a meet semi-lattice from various forms of input data.

INPUT:

  • data, *args, **options – data and options that will be passed down to Poset() to construct a poset that is also a meet semilattice.

EXAMPLES:

Using data that defines a poset:

sage: MeetSemilattice([[1,2],[3],[3]])
Finite meet-semilattice containing 4 elements

sage: MeetSemilattice([[1,2],[3],[3]], cover_relations = True)
Finite meet-semilattice containing 4 elements

Using a previously constructed poset:

sage: P = Poset([[1,2],[3],[3]])
sage: L = MeetSemilattice(P); L
Finite meet-semilattice containing 4 elements
sage: type(L)
<class 'sage.combinat.posets.lattices.FiniteMeetSemilattice_with_category'>

If the data is not a lattice, then an error is raised:

sage: elms = [1,2,3,4,5,6,7]
sage: rels = [[1,2],[3,4],[4,5],[2,5]]
sage: MeetSemilattice((elms, rels))
Traceback (most recent call last):
...
ValueError: Not a meet semilattice.