Finite lattices and semilattices

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

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

List of (semi)lattice methods

Meet and join

meet() Return the meet of given elements.
join() Return the join of given elements.
meet_matrix() Return the matrix of meets of all elements of the meet semi-lattice.
join_matrix() Return the matrix of joins of all elements of the join semi-lattice.

Properties of the lattice

is_distributive() Return True if the lattice is distributive.
is_modular() Return True if the lattice is modular.
is_lower_semimodular() Return True if the lattice is lower semimodular.
is_upper_semimodular() Return True if the lattice is upper semimodular.
is_join_semidistributive() Return True if the lattice is join-semidistributive.
is_meet_semidistributive() Return True if the lattice is meet-semidistributive.
is_atomic() Return True if every element of the lattice can be written as a join of atoms.
is_coatomic() Return True if every element of the lattice can be written as a meet of coatoms.
is_geometric() Return True if the lattice is atomic and upper semimodular.
is_complemented() Return True if every element of the lattice has at least one complement.
is_sectionally_complemented() Return True if every interval from the bottom is complemented.
is_relatively_complemented() Return True if every interval of the lattice is complemented.
is_pseudocomplemented() Return True if every element of the lattice has a pseudocomplement.
is_orthocomplemented() Return True if the lattice has an orthocomplementation.
is_supersolvable() Return True if the lattice is supersolvable.
is_planar() Return True if the lattice has an upward planar drawing.
is_dismantlable() Return True if the lattice is dismantlable.
is_vertically_decomposable() Return True if the lattice is vertically decomposable.
breadth() Return the breadth of the lattice.

Elements and sublattices

atoms() Return the list of elements covering the bottom element.
coatoms() Return the list of elements covered by the top element.
double_irreducibles() Return the list of double irreducible elements.
complements() Return the list of complements of an element, or the dictionary of complements for all elements.
pseudocomplement() Return the pseudocomplement of an element.
is_modular_element() Return True if given element is modular in the lattice.
sublattice() Return sublattice generated by list of elements.
is_sublattice() Return True if the lattice is a sublattice of given lattice.
sublattices() Return all sublattices of the lattice.
sublattices_lattice() Return the lattice of sublattices.
maximal_sublattices() Return maximal sublattices of the lattice.
frattini_sublattice() Return the intersection of maximal sublattices of the lattice.
vertical_decomposition() Return the vertical decomposition of the lattice.
canonical_joinands() Return the canonical joinands of an element.

Miscellaneous

moebius_algebra() Return the Möbius algebra of the lattice.
quantum_moebius_algebra() Return the quantum Möbius algebra of the 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

For non-facade lattices operator + works for join:

sage: L = Posets.PentagonPoset(facade=False)
sage: L(1)+L(2)
4
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

atoms()

Return the atoms of this lattice.

An atom of a lattice is an element covering the bottom element.

See also

coatoms()

EXAMPLES:

sage: L = Posets.DivisorLattice(60)
sage: sorted(L.atoms())
[2, 3, 5]

TESTS:

sage: LatticePoset().atoms()
[]
sage: LatticePoset({0: []}).atoms()
[]
breadth(certificate=False)

Return the breadth of the lattice.

The breadth of a lattice is the largest integer \(n\) such that any join of elements \(x_1, x_2, \ldots, x_{n+1}\) is join of a proper subset of \(x_i\).

This can be also characterized by sublattices: a lattice of breadth at least \(n\) contains a sublattice isomorphic to the Boolean lattice of \(2^n\) elements.

INPUT:

  • certificate – (boolean; default: False) – whether to return an integer (the breadth) or a certificate, i.e. a biggest set whose join differs from the join of any subset.

EXAMPLES:

sage: D10 = Posets.DiamondPoset(10)
sage: D10.breadth()
2

sage: B3 = Posets.BooleanLattice(3)
sage: B3.breadth()
3
sage: B3.breadth(certificate=True)
[1, 2, 4]

ALGORITHM:

For a lattice to have breadth at least \(n\), it must have an \(n\)-element antichain \(A\) with join \(j\). Element \(j\) must cover at least \(n\) elements. There must also be \(n-2\) levels of elements between \(A\) and \(j\). So we start by searching elements that could be our \(j\) and then just check possible antichains \(A\).

TESTS:

sage: Posets.ChainPoset(0).breadth()
0
sage: Posets.ChainPoset(1).breadth()
1
canonical_joinands(e)

Return the canonical joinands of \(e\).

The canonical joinands of an element \(e\) in the lattice \(L\) is the subset \(S \subseteq L\) such that 1) the join of \(S\) is \(e\), and 2) if the join of some other subset \(S'\) of is also \(e\), then for every element \(s \in S\) there is an element \(s' \in S'\) such that \(s \le s'\).

Informally said this is the set of lowest possible elements with given join. It exists for every element if and only if the lattice is join-semidistributive. Canonical joinands are always join-irreducibles.

INPUT:

  • e – an element of the lattice

OUTPUT:

  • canonical joinands as a list, if it exists; if not, None

EXAMPLES:

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

sage: L = LatticePoset({1: [2, 3], 2: [4, 5], 3: [6], 4: [6],
....: 5: [6]})
sage: L.canonical_joinands(6) is None
True

TESTS:

LatticePoset({1: []}).canonical_joinands(1)
[1]
coatoms()

Return the co-atoms of this lattice.

A co-atom of a lattice is an element covered by the top element.

See also

atoms()

EXAMPLES:

sage: L = Posets.DivisorLattice(60)
sage: sorted(L.coatoms())
[12, 20, 30]

TESTS:

sage: LatticePoset().coatoms()
[]
sage: LatticePoset({0: []}).coatoms()
[]
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 lattice 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()

sage: Posets.ChainPoset(0).complements()
{}
sage: Posets.ChainPoset(1).complements()
{0: [0]}
sage: Posets.ChainPoset(2).complements()
{0: [1], 1: [0]}
double_irreducibles()

Return the list of double irreducible elements of this lattice.

A double irreducible element of a lattice is an element covering and covered by exactly one element. In other words it is neither a meet nor a join of any elements.

EXAMPLES:

sage: L = Posets.DivisorLattice(12)
sage: sorted(L.double_irreducibles())
[3, 4]

sage: L = Posets.BooleanLattice(3)
sage: L.double_irreducibles()
[]

TESTS:

sage: LatticePoset().double_irreducibles()
[]
sage: Posets.ChainPoset(2).double_irreducibles()
[]
frattini_sublattice()

Return the Frattini sublattice of the lattice.

The Frattini sublattice \(\Phi(L)\) is the intersection of all proper maximal sublattices of \(L\). It is also the set of “non-generators” - if the sublattice generated by set \(S\) of elements is whole lattice, then also \(S \setminus \Phi(L)\) generates whole 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: sorted(L.frattini_sublattice().list())
[1, 2, 4, 10, 19, 22, 33]
is_atomic()

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

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

EXAMPLES:

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

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

TESTS:

sage: LatticePoset({}).is_atomic()
True

NOTES:

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

REFERENCES:

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

See also

is_coatomic()

is_coatomic()

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

A lattice is coatomic if every element can be written as a meet of coatoms; i.e. if the dual of the lattice is atomic.

EXAMPLES:

sage: L = Posets.BooleanLattice(3)
sage: L.is_coatomic()
True

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

TESTS:

sage: LatticePoset({}).is_coatomic()
True

See also

is_atomic()

is_complemented(certificate=False)

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

A lattice is complemented if every element has at least one complement.

INPUT:

  • certificate – (default: False) whether to return a certificate

OUTPUT:

  • If certificate=True return either (True, None) or (False, e), where e is an element without a complement. If certificate=False return True or False.

See also

complements()

EXAMPLES:

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

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

TESTS:

sage: [Posets.ChainPoset(i).is_complemented() for i in range(5)]
[True, True, True, False, False]
is_dismantlable(certificate=False)

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

An \(n\)-element lattice \(L_n\) is dismantlable if there is a sublattice chain \(L_{n-1} \supset L_{n-2}, \supset \cdots, \supset L_0\) so that every \(L_i\) is a sublattice of \(L_{i+1}\) with one element less, and \(L_0\) is the empty lattice. In other words, a dismantlable lattice can be reduced to empty lattice removing doubly irreducible element one by one.

INPUT:

  • certificate (boolean) – Whether to return a certificate.
    • If certificate = False (default), returns True or False accordingly.
    • If certificate = True, returns:
      • (True, elms) when the lattice is dismantlable, where elms is elements listed in a possible removing order.
      • (False, crown) when the lattice is not dismantlable, where crown is a subposet of \(2k\) elements \(a_1, \ldots, a_k, b_1, \ldots, b_k\) with covering relations \(a_i \lessdot b_i\) and \(a_i \lessdot b_{i+1}\) for \(i \in [1, \ldots, k-1]\), and \(a_k \lessdot b_1\).

EXAMPLES:

sage: DL12 = LatticePoset((divisors(12), attrcall("divides")))
sage: DL12.is_dismantlable()
True
sage: DL12.is_dismantlable(certificate=True)
(True, [4, 2, 1, 3, 6, 12])

sage: B3 = Posets.BooleanLattice(3)
sage: B3.is_dismantlable()
False
sage: B3.is_dismantlable(certificate=True)
(False, Finite poset containing 6 elements)

Every planar lattice is dismantlable. Converse is not true:

sage: L = LatticePoset( ([], [[0, 1], [0, 2], [0, 3], [0, 4],
....:                         [1, 7], [2, 6], [3, 5], [4, 5],
....:                         [4, 6], [4, 7], [5, 8], [6, 8],
....:                         [7, 8]]) )
sage: L.is_dismantlable()
True
sage: L.is_planar()
False

TESTS:

sage: Posets.ChainPoset(0).is_dismantlable()
True
sage: Posets.ChainPoset(1).is_dismantlable()
True

sage: L = LatticePoset(DiGraph('L@_?W?E?@CCO?A?@??_?O?Jw????C?'))
sage: L.is_dismantlable()
False
sage: c = L.is_dismantlable(certificate=True)[1]
sage: (3 in c, 12 in c, 9 in c)
(True, False, True)
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_geometric()

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

A lattice is geometric if it is both atomic and upper semimodular.

EXAMPLES:

Canonical example is the lattice of partitions of finite set ordered by refinement:

sage: S = SetPartitions(3)
sage: L = LatticePoset( (S, lambda a, b: S.is_less_than(a, b)) )
sage: L.is_geometric()
True

Smallest example of geometric lattice that is not modular:

sage: L = LatticePoset(DiGraph('K]?@g@S?q?M?@?@?@?@?@?@??'))
sage: L.is_geometric()
True
sage: L.is_modular()
False

Two non-examples:

sage: L = LatticePoset({1:[2, 3, 4], 2:[5, 6], 3:[5], 4:[6], 5:[7], 6:[7]})
sage: L.is_geometric()  # Graded, but not upper semimodular
False
sage: L = Posets.ChainPoset(3)
sage: L.is_geometric()  # Modular, but not atomic
False

TESTS:

sage: LatticePoset({}).is_geometric()
True
sage: LatticePoset({1:[]}).is_geometric()
True
is_join_semidistributive()

Return True if the lattice is join-semidistributive, and False otherwise.

A lattice is join-semidistributive if \(e \vee x = e \vee y\) implicates \(e \vee x = e \vee (x \wedge y)\) for all elements \(e, x, y\) in the lattice.

EXAMPLES:

sage: T4 = Posets.TamariLattice(4)
sage: T4.is_join_semidistributive()
True
sage: L = LatticePoset({1:[2, 3], 2:[4, 5], 3:[5, 6],
....:                   4:[7], 5:[7], 6:[7]})
sage: L.is_join_semidistributive()
False

TESTS:

sage: LatticePoset().is_join_semidistributive()
True

Smallest lattice that fails the quick check:

sage: L = LatticePoset(DiGraph('IY_T@A?CC_@?W?O@??'))
sage: L.is_join_semidistributive()
False

Confirm that trac ticket #21340 is fixed:

sage: Posets.BooleanLattice(3).is_join_semidistributive()
True
is_lower_semimodular(certificate=False)

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

A lattice is lower semimodular if any pair of elements with a common upper cover have also a common lower cover.

INPUT:

  • certificate – (default: False) Whether to return a certificate if the lattice is not lower semimodular.

OUTPUT:

  • If certificate=False return True or False. If certificate=True return either (True, None) or (False, (a, b)), where \(a\) and \(b\) are covered by their join but do no cover their meet.

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

sage: L = LatticePoset(DiGraph('IS?`?AAOE_@?C?_@??'))
sage: L.is_lower_semimodular(certificate=True)
(False, (4, 2))
is_meet_semidistributive()

Return True if the lattice is meet-semidistributive, and False otherwise.

A lattice is meet-semidistributive if \(e \wedge x = e \wedge y\) implicates \(e \wedge x = e \wedge (x \vee y)\) for all elements \(e, x, y\) in the lattice.

EXAMPLES:

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

TESTS:

sage: LatticePoset().is_meet_semidistributive()
True

Smallest lattice that fails the quick check:

sage: L = LatticePoset(DiGraph('IY_T@A?CC_@?W?O@??'))
sage: L.is_join_semidistributive()
False

Confirm that trac ticket #21340 is fixed:

sage: Posets.BooleanLattice(4).is_join_semidistributive()
True
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_orthocomplemented(unique=False)

Return True if the lattice admits an orthocomplementation, and False otherwise.

An orthocomplementation of a lattice is a function defined for every element \(e\) and marked as \(e^{\bot}\) such that 1) they are complements, i.e. \(e \vee e^{\bot}\) is the top element and \(e \wedge e^{\bot}\) is the bottom element, 2) it is involution, i.e. \({(e^{\bot})}^{\bot} = e\), and 3) it is order-reversing, i.e. if \(a < b\) then \(b^{\bot} < a^{\bot}\).

INPUT:

  • unique, a Boolean – If True, return True only if the lattice has exactly one orthocomplementation. If False (the default), return True when the lattice has at least one orthocomplementation.

EXAMPLES:

sage: D5 = Posets.DiamondPoset(5)
sage: D5.is_orthocomplemented()
False

sage: D6 = Posets.DiamondPoset(6)
sage: D6.is_orthocomplemented()
True
sage: D6.is_orthocomplemented(unique=True)
False

sage: hexagon = LatticePoset({0:[1, 2], 1:[3], 2:[4], 3:[5], 4:[5]})
sage: hexagon.is_orthocomplemented(unique=True)
True

TESTS:

sage: [Posets.ChainPoset(i).is_orthocomplemented() for i in range(4)]
[True, True, True, False]
is_planar()

Return True if the lattice is upward planar, and False otherwise.

A lattice is upward planar if its Hasse diagram has a planar drawing in the \(\mathbb{R}^2\) plane, in such a way that \(x\) is strictly below \(y\) (on the vertical axis) whenever \(x<y\) in the lattice.

Note that the scientific litterature on posets often omits “upward” and shortens it to “planar lattice” (e.g. [GW14]), which can cause confusion with the notion of graph planarity in graph theory.

Note

Not all lattices which are planar – in the sense of graph planarity – admit such a planar drawing (see example below).

ALGORITHM:

Using the result from [Platt76], this method returns its result by testing that the Hasse diagram of the lattice is planar (in the sense of graph theory) when an edge is added between the top and bottom elements.

EXAMPLES:

The Boolean lattice of \(2^3\) elements is not upward planar, even if it’s covering relations graph is planar:

sage: B3 = Posets.BooleanLattice(3)
sage: B3.is_planar()
False
sage: G = B3.cover_relations_graph()
sage: G.is_planar()
True

Ordinal product of planar lattices is obviously planar. Same does not apply to Cartesian products:

sage: P = Posets.PentagonPoset()
sage: Pc = P.product(P)
sage: Po = P.ordinal_product(P)
sage: Pc.is_planar()
False
sage: Po.is_planar()
True

TESTS:

sage: Posets.ChainPoset(0).is_planar()
True
sage: Posets.ChainPoset(1).is_planar()
True

REFERENCES:

[GW14]G. Gratzer and F. Wehrung, Lattice Theory: Special Topics and Applications Vol. 1, Springer, 2014.
[Platt76]C. R. Platt, Planar lattices and planar graphs, Journal of Combinatorial Theory Series B, Vol 21, no. 1 (1976): 30-39.
is_pseudocomplemented(certificate=False)

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

A lattice is (meet-)pseudocomplemented if every element \(e\) has a pseudocomplement \(e^\star\), i.e. the greatest element such that the meet of \(e\) and \(e^\star\) is the bottom element.

See Wikipedia article Pseudocomplement.

INPUT:

  • certificate – (default: False) whether to return a certificate

OUTPUT:

  • If certificate=True return either (True, None) or (False, e), where e is an element without a pseudocomplement. If certificate=False return True or False.

EXAMPLES:

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

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

TESTS:

sage: LatticePoset({}).is_pseudocomplemented()
True
is_relatively_complemented(certificate=False)

Return True if the lattice is relatively complemented, and False otherwise.

A lattice is relatively complemented if every interval of it is a complemented lattice.

INPUT:

  • certificate – (default: False) Whether to return a certificate if the lattice is not relatively complemented.

OUTPUT:

  • If certificate=True return either (True, None) or (False, (a, b, c)), where \(b\) is the only element that covers \(a\) and is covered by \(c\). If certificate=False return True or False.

EXAMPLES:

sage: L = LatticePoset({1: [2, 3, 4, 8], 2: [5, 6], 3: [5, 7],
....:                   4: [6, 7], 5: [9], 6: [9], 7: [9], 8: [9]})
sage: L.is_relatively_complemented()
True

sage: L = Posets.PentagonPoset()
sage: L.is_relatively_complemented()
False

Relatively complemented lattice must be both atomic and coatomic. Implication to other direction does not hold:

sage: L = LatticePoset({0: [1, 2, 3, 4, 5], 1: [6, 7], 2: [6, 8],
....:                   3: [7, 8, 9], 4: [9, 11], 5: [9, 10],
....:                   6: [10, 11], 7: [12], 8: [12], 9: [12],
....:                   10: [12], 11: [12]})
sage: L.is_atomic() and L.is_coatomic()
True
sage: L.is_relatively_complemented()
False

We can also get a non-complemented 3-element interval:

sage: L.is_relatively_complemented(certificate=True)
(False, (1, 6, 11))

TESTS:

sage: [Posets.ChainPoset(i).is_relatively_complemented() for
....:  i in range(5)]
[True, True, True, False, False]

Usually a lattice that is not relatively complemented contains elements \(l\), \(m\), and \(u\) such that \(r(l) + 1 = r(m) = r(u) - 1\), where \(r\) is the rank function and \(m\) is the only element in the interval \([l, u]\). We construct an example where this does not hold:

sage: B3 = Posets.BooleanLattice(3)
sage: B5 = Posets.BooleanLattice(5)
sage: B3 = B3.subposet([e for e in B3 if e not in [0, 7]])
sage: B5 = B5.subposet([e for e in B5 if e not in [0, 31]])
sage: B3 = B3.hasse_diagram()
sage: B5 = B5.relabel(lambda x: x+10).hasse_diagram()
sage: G = B3.union(B5)
sage: G.add_edge(B3.sources()[0], B5.neighbors_in(B5.sinks()[0])[0])
sage: L = LatticePoset(Poset(G).with_bounds())
sage: L.is_relatively_complemented()
False
is_sectionally_complemented(certificate=False)

Return True if the lattice is sectionally complemented, and False otherwise.

A lattice is sectionally complemented if all intervals from the bottom element interpreted as sublattices are complemented lattices.

INPUT:

  • certificate – (default: False) Whether to return a certificate if the lattice is not sectionally complemented.

OUTPUT:

  • If certificate=False return True or False. If certificate=True return either (True, None) or (False, (t, e)), where \(t\) is an element so that in the sublattice from the bottom element to \(t\) has no complement for element \(e\).

EXAMPLES:

Smallest examples of a complemented but not sectionally complemented lattice and a sectionally complemented but not relatively complemented lattice:

sage: L = Posets.PentagonPoset()
sage: L.is_complemented()
True
sage: L.is_sectionally_complemented()
False

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

Getting a certificate:

sage: L = LatticePoset(DiGraph('HYOgC?C@?C?G@??'))
sage: L.is_sectionally_complemented(certificate=True)
(False, (6, 1))

TESTS:

sage: [Posets.ChainPoset(i).is_sectionally_complemented() for i in range(5)]
[True, True, True, False, False]
is_sublattice(other)

Return True if the lattice is a sublattice of other, and False otherwise.

Lattice \(K\) is a sublattice of \(L\) if \(K\) is an (induced) subposet of \(L\) and closed under meet and join of \(L\).

Note

This method does not check whether the lattice is a isomorphic (i.e., up to relabeling) sublattice of other, but only if other directly contains the lattice as an sublattice.

EXAMPLES:

A pentagon sublattice in a non-modular lattice:

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

This pentagon is a subposet but not closed under join, hence not a sublattice:

sage: N5_ = LatticePoset({1: [2, 3], 2: [4], 3: [7], 4: [7]})
sage: N5_.is_induced_subposet(L)
True
sage: N5_.is_sublattice(L)
False

TESTS:

sage: E = LatticePoset({})
sage: P = Posets.PentagonPoset()
sage: E.is_sublattice(P)
True

sage: P1 = LatticePoset({'a':['b']})
sage: P2 = P1.dual()
sage: P1.is_sublattice(P2)
False

sage: P = MeetSemilattice({0: [1]})
sage: E.is_sublattice(P)
Traceback (most recent call last):
...
TypeError: other is not a lattice
sage: P = JoinSemilattice({0: [1]})
sage: E.is_sublattice(P)
Traceback (most recent call last):
...
TypeError: other is not a lattice
is_supersolvable(certificate=False)

Return True if the lattice is supersolvable, 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\). Equivalent definition is that the sublattice generated by \(C\) and any other chain is distributive.

INPUT:

  • certificate – (default: False) whether to return a certificate

OUTPUT:

  • If certificate=True return either (False, None) or (True, C), where C is a maximal chain of modular elements. If certificate=False return True or False.

EXAMPLES:

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

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

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_supersolvable(certificate=True)
(True, [1, 2, 5, 7])
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

TESTS:

sage: LatticePoset().is_supersolvable()
True
is_upper_semimodular(certificate=False)

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

A lattice is upper semimodular if any pair of elements with a common lower cover have also a common upper cover.

INPUT:

  • certificate – (default: False) Whether to return a certificate if the lattice is not upper semimodular.

OUTPUT:

  • If certificate=False return True or False. If certificate=True return either (True, None) or (False, (a, b)), where \(a\) and \(b\) covers their meet but are not covered by their join.

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 = LatticePoset(posets.IntegerPartitions(4))
sage: L.is_upper_semimodular()
True

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

TESTS:

sage: all(Posets.ChainPoset(i).is_upper_semimodular() for i in range(5))
True
is_vertically_decomposable()

Return True if the lattice is vertically decomposable, and False otherwise.

A lattice is vertically decomposable if it has an element that is comparable to all elements and is neither the bottom nor the top element.

Informally said, a lattice is vertically decomposable if it can be seen as two lattices “glued” by unifying the top element of first lattice to the bottom element of second one.

EXAMPLES:

sage: L = LatticePoset( ([1, 2, 3, 6, 12, 18, 36],
....:     attrcall("divides")) )
sage: L.is_vertically_decomposable()
True
sage: Posets.TamariLattice(4).is_vertically_decomposable()
False

TESTS:

sage: [Posets.ChainPoset(i).is_vertically_decomposable() for i in
....:     range(5)]
[False, False, False, True, True]
maximal_sublattices()

Return maximal (proper) sublattices 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: maxs = L.maximal_sublattices()
sage: len(maxs)
7
sage: sorted(maxs[0].list())
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 16, 18, 19, 22, 33]
moebius_algebra(R)

Return the Möbius algebra of self over R.

EXAMPLES:

sage: L = posets.BooleanLattice(4)
sage: L.moebius_algebra(QQ)
Moebius algebra of Finite lattice containing 16 elements over Rational Field
quantum_moebius_algebra(q=None)

Return the quantum Möbius algebra of self with parameter q.

INPUT:

  • q – (optional) the deformation parameter \(q\)

EXAMPLES:

sage: L = posets.BooleanLattice(4)
sage: L.quantum_moebius_algebra()
Quantum Moebius algebra of Finite lattice containing 16 elements
 with q=q over Univariate Laurent Polynomial Ring in q over Integer Ring
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
sublattices()

Return all sublattices of the lattice.

EXAMPLES:

sage: L = LatticePoset({1: [2, 3, 4], 2:[5], 3:[5, 6], 4:[6],
....:                   5:[7], 6:[7]})
sage: sublats = L.sublattices(); len(sublats)
54
sage: sublats[3]
Finite lattice containing 4 elements
sage: sublats[3].list()
[1, 2, 3, 5]

TESTS:

A subposet that is a lattice but not a sublattice:

sage: L = LatticePoset({1: [2, 3], 2:[4], 3:[4], 4:[5]})
sage: sl = L.sublattices()
sage: LatticePoset({1: [2, 3], 2:[5], 3:[5]}) in sl
False

\(n\)-element chain has \(2^n\) sublattices (also tests empty lattice):

sage: [len(Posets.ChainPoset(n).sublattices()) for n in range(4)]
[1, 2, 4, 8]
sublattices_lattice(element_constructor='lattice')

Return the lattice of sublattices.

Every element of the returned lattice is a sublattice and they are ordered by containment; that is, atoms are one-element lattices, coatoms are maximal sublattices of the original lattice and so on.

INPUT:

  • element_constructor – string; can be one of the following:
    • 'lattice' (default) elements of the lattice will be lattices that correspond to sublattices of the original lattice
    • 'tuple' - elements are tuples of elements of the sublattices of the original lattice
    • 'integer' - elements are plain integers

EXAMPLES:

sage: D4 = Posets.DiamondPoset(4)
sage: sll = D4.sublattices_lattice(element_constructor='tuple')
sage: sll.coatoms()  # = maximal sublattices of the original lattice
[(0, 1, 3), (0, 2, 3)]

sage: L = Posets.DivisorLattice(12)
sage: sll = L.sublattices_lattice()
sage: L.is_dismantlable() == (len(sll.atoms()) == sll.rank())
True

TESTS:

sage: E = Posets.ChainPoset(0)
sage: E.sublattices_lattice()
Finite lattice containing 1 elements

sage: C3 = Posets.ChainPoset(3)
sage: sll = C3.sublattices_lattice(element_constructor='integer')
sage: sll.is_isomorphic(Posets.BooleanLattice(3))
True
vertical_decomposition(elements_only=False)

Return sublattices from the vertical decomposition of the lattice.

Let \(d_1, \ldots, d_n\) be elements (excluding the top and bottom elements) comparable to every element of the lattice. Let \(b\) be the bottom element and \(t\) be the top element. This function returns either a list \(d_1, \ldots, d_n\), or the list of intervals \([b, d_1], [d_1, d_2], \ldots, [d_{n-1}, d_n], [d_n, t]\) as lattices.

Informally said, this returns the lattice split into parts at every single-element “cutting point”.

INPUT:

  • elements_only - if True, return the list of decomposing elements as defined above; if False (the default), return the list of sublattices so that the lattice is a vertical composition of them.

EXAMPLES:

Number 6 is divided by 1, 2, and 3, and it divides 12, 18 and 36:

sage: L = LatticePoset( ([1, 2, 3, 6, 12, 18, 36],
....:     attrcall("divides")) )
sage: parts = L.vertical_decomposition()
sage: [lat.list() for lat in parts]
[[1, 2, 3, 6], [6, 12, 18, 36]]
sage: L.vertical_decomposition(elements_only=True)
[6]

TESTS:

sage: [Posets.ChainPoset(i).vertical_decomposition(elements_only=True)
....:     for i in range(5)]
[[], [], [], [1], [1, 2]]
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.

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

For non-facade lattices operator * works for meet:

sage: L = Posets.PentagonPoset(facade=False)
sage: L(1)*L(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
pseudocomplement(element)

Return the pseudocomplement of element, if it exists.

The (meet-)pseudocomplement is the greatest element whose meet with given element is the bottom element. I.e. in a meet-semilattice with bottom element \(\hat{0}\) the pseudocomplement of an element \(e\) is the element \(e^\star\) such that \(e \wedge e^\star = \hat{0}\) and \(e' \le e^\star\) if \(e \wedge e' = \hat{0}\).

See Wikipedia article Pseudocomplement.

INPUT:

  • element – an element of the lattice.

OUTPUT:

An element of the lattice or None if the pseudocomplement does not exist.

EXAMPLES:

The pseudocompelement’s pseudocomplement is not always the original element:

sage: L = LatticePoset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6]})
sage: L.pseudocomplement(2)
5
sage: L.pseudocomplement(5)
4

An element can have complements but no pseudocomplement, or vice versa:

sage: L = LatticePoset({0: [1, 2], 1: [3, 4, 5], 2: [5], 3: [6],
....:                   4: [6], 5: [6]})
sage: L.complements(1), L.pseudocomplement(1)
([], 2)
sage: L.complements(2), L.pseudocomplement(2)
([3, 4], None)

TESTS:

sage: L = LatticePoset({'a': []})
sage: L.pseudocomplement('a')
'a'
sage: L = LatticePoset({'a': ['b'], 'b': ['c']})
sage: [L.pseudocomplement(e) for e in ['a', 'b', 'c']]
['c', 'a', 'a']
sage.combinat.posets.lattices.JoinSemilattice(data=None, *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: JoinSemilattice({'a': ['b', 'c'], 'b': ['d', 'e'],
....:                  'c': ['d', 'e'], 'd': ['f'], 'e': ['f']})
Traceback (most recent call last):
...
LatticeError: no join for b and c
sage.combinat.posets.lattices.LatticePoset(data=None, *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:

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 meet-semilattice: no bottom element

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=None, *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: MeetSemilattice({'a': ['b', 'c'], 'b': ['d', 'e'],
....:                  'c': ['d', 'e'], 'd': ['f'], 'e': ['f']})
Traceback (most recent call last):
...
LatticeError: no meet for e and d