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 all elements with common upper cover have a common lower cover. |
is_upper_semimodular() |
Return True if all elements with common lower cover have a common upper cover. |
is_semidistributive() |
Return True if the lattice is both join- and meet-semidistributive. |
is_join_semidistributive() |
Return True if the lattice is join-semidistributive. |
is_meet_semidistributive() |
Return True if the lattice is meet-semidistributive. |
is_join_distributive() |
Return True if the lattice is join-distributive. |
is_meet_distributive() |
Return True if the lattice is meet-distributive. |
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_extremal() |
Return True if the lattice is extremal. |
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_cosectionally_complemented() |
Return True if every interval to the top 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 (meet-)pseudocomplement. |
is_join_pseudocomplemented() |
Return True if every element of the lattice has a join-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_interval_dismantlable() |
Return True if the lattice is interval dismantlable. |
is_sublattice_dismantlable() |
Return True if the lattice is sublattice dismantlable. |
is_stone() |
Return True if the lattice is a Stone lattice. |
is_trim() |
Return True if the lattice is a trim lattice. |
is_vertically_decomposable() |
Return True if the lattice is vertically decomposable. |
is_simple() |
Return True if the lattice has no nontrivial congruences. |
is_isoform() |
Return True if all congruences of the lattice consists of isoform blocks. |
is_uniform() |
Return True if all congruences of the lattice consists of equal-sized blocks. |
is_regular() |
Return True if all congruences of lattice are determined by any of the congruence blocks. |
is_subdirectly_reducible() |
Return True if the lattice is a sublattice of the product of smaller lattices. |
is_constructible_by_doublings() |
Return True if the lattice is constructible by doublings from the one-element lattice. |
breadth() |
Return the breadth of the lattice. |
Specific elements
atoms() |
Return elements covering the bottom element. |
coatoms() |
Return elements covered by the top element. |
double_irreducibles() |
Return double irreducible elements. |
join_primes() |
Return the join prime elements. |
meet_primes() |
Return the meet prime 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. |
is_left_modular_element() |
Return True if given element is left modular in the lattice. |
neutral_elements() |
Return neutral elements of the lattice. |
canonical_joinands() |
Return the canonical joinands of an element. |
canonical_meetands() |
Return the canonical meetands of an element. |
Sublattices
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. |
isomorphic_sublattices_iterator() |
Return an iterator over the sublattices isomorphic to given lattice. |
maximal_sublattices() |
Return maximal sublattices of the lattice. |
frattini_sublattice() |
Return the intersection of maximal sublattices of the lattice. |
skeleton() |
Return the skeleton of the lattice. |
center() |
Return the sublattice of complemented neutral elements. |
vertical_decomposition() |
Return the vertical decomposition of the lattice. |
Miscellaneous
moebius_algebra() |
Return the Möbius algebra of the lattice. |
quantum_moebius_algebra() |
Return the quantum Möbius algebra of the lattice. |
vertical_composition() |
Return ordinal sum of lattices with top/bottom element unified. |
day_doubling() |
Return the lattice with Alan Day’s doubling construction of a subset. |
adjunct() |
Return the adjunct with other lattice. |
subdirect_decomposition() |
Return the subdirect decomposition of the lattice. |
congruence() |
Return the congruence generated by lists of elements. |
quotient() |
Return the quotient lattice by a congruence. |
congruences_lattice() |
Return the lattice of congruences. |
-
sage.combinat.posets.lattices.
FiniteJoinSemilattice
¶ 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).
sage: P = Poset([[1,2],[3],[3]]) sage: J = JoinSemilattice(P) sage: TestSuite(J).run()
-
sage.combinat.posets.lattices.
FiniteLatticePoset
¶ 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).
sage: P = Poset([[1,2],[3],[3]]) sage: L = LatticePoset(P) sage: TestSuite(L).run()
-
sage.combinat.posets.lattices.
FiniteMeetSemilattice
¶ 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).
sage: P = Poset([[1,2],[3],[3]]) sage: M = MeetSemilattice(P) sage: TestSuite(M).run()
-
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 3 elements sage: JoinSemilattice([[1,2],[3],[3]], cover_relations = True) Finite join-semilattice containing 3 elements
Using a previously constructed poset:
sage: P = Poset([[1,2],[3],[3]]) sage: J = JoinSemilattice(P); J Finite join-semilattice containing 3 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 3 elements sage: LatticePoset([[1,2],[3],[3]], cover_relations = True) Finite lattice containing 3 elements
Using a previously constructed poset:
sage: P = Poset([[1,2],[3],[3]]) sage: L = LatticePoset(P); L Finite lattice containing 3 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() Category of facade finite enumerated lattice posets 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 3 elements sage: MeetSemilattice([[1,2],[3],[3]], cover_relations = True) Finite meet-semilattice containing 3 elements
Using a previously constructed poset:
sage: P = Poset([[1,2],[3],[3]]) sage: L = MeetSemilattice(P); L Finite meet-semilattice containing 3 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