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 ORx
– 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 isk
, whereself.linear_extension()[k]
is the join (least upper bound) ofself.linear_extension()[i]
andself.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
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
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. IfNone
(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.
See also
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, andFalse
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
()¶ Return
True
if the lattice is coatomic, andFalse
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_complemented
(certificate=False)¶ Return
True
if the lattice is complemented, andFalse
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)
, wheree
is an element without a complement. Ifcertificate=False
returnTrue
orFalse
.
See also
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, andFalse
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), returnsTrue
orFalse
accordingly. - If
certificate = True
, returns:(True, elms)
when the lattice is dismantlable, whereelms
is elements listed in a possible removing order.(False, crown)
when the lattice is not dismantlable, wherecrown
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\).
- If
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, andFalse
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, andFalse
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, andFalse
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.
See also
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 andFalse
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
returnTrue
orFalse
. Ifcertificate=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 also
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, andFalse
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.
See also
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 andFalse
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, ifL
isNone
, 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.
See also
is_upper_semimodular()
,is_lower_semimodular()
andis_modular_element()
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
ifx
is a modular element andFalse
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 elementsEXAMPLES:
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, andFalse
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 – IfTrue
, returnTrue
only if the lattice has exactly one orthocomplementation. IfFalse
(the default), returnTrue
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, andFalse
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, andFalse
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)
, wheree
is an element without a pseudocomplement. Ifcertificate=False
returnTrue
orFalse
.
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, andFalse
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\). Ifcertificate=False
returnTrue
orFalse
.
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, andFalse
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
returnTrue
orFalse
. Ifcertificate=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 ofother
, andFalse
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 ifother
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, andFalse
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)
, whereC
is a maximal chain of modular elements. Ifcertificate=False
returnTrue
orFalse
.
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 andFalse
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
returnTrue
orFalse
. Ifcertificate=True
return either(True, None)
or(False, (a, b))
, where \(a\) and \(b\) covers their meet but are not covered by their join.
See also
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, andFalse
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.
See also
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
overR
.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 parameterq
.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
- ifTrue
, return the list of decomposing elements as defined above; ifFalse
(the default), return the list of sublattices so that the lattice is a vertical composition of them.
See also
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 ORx
– 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 isk
, whereself.linear_extension()[k]
is the meet (greatest lower bound) ofself.linear_extension()[i]
andself.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 toPoset()
to construct a poset that is also a join semilattice
See also
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 toPoset()
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 toPoset()
to construct a poset that is also a meet semilattice.
See also
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