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