Finite semilattices and lattices¶
This module implements finite (semi)lattices. It defines:
FiniteJoinSemilattice |
A class for finite join semilattices. |
FiniteMeetSemilattice |
A class for finite meet semilattices. |
FiniteLatticePoset |
A class for finite lattices. |
JoinSemilattice() |
Construct a join semi-lattice. |
LatticePoset() |
Construct a lattice. |
MeetSemilattice() |
Construct a meet semi-lattice. |
List of (semi)lattice methods¶
complements() |
Return the list of complements of an element, or the dictionary of complements for all elements. |
is_atomic() |
Return True if the lattice is atomic. |
is_complemented() |
Return True if the lattice is complemented. |
is_distributive() |
Return True if the lattice is distributive. |
is_lower_semimodular() |
Return True if the lattice is lower semimodular. |
is_modular() |
Return True if the lattice is lower modular. |
is_modular_element() |
Return True if given element is modular in the lattice. |
is_upper_semimodular() |
Return True if the lattice is upper semimodular. |
is_supersolvable() |
Return True if the lattice is supersolvable. |
join() |
Return the join of given elements in the join semi-lattice. |
join_matrix() |
Return the matrix of joins of all elements of the join semi-lattice. |
meet() |
Return the meet of given elements in the meet semi-lattice. |
meet_matrix() |
Return the matrix of meets of all elements of the meet semi-lattice. |
-
class
sage.combinat.posets.lattices.
FiniteJoinSemilattice
(hasse_diagram, elements, category, facade, key)¶ Bases:
sage.combinat.posets.posets.FinitePoset
We assume that the argument passed to FiniteJoinSemilattice is the poset of a join-semilattice (i.e. a poset with least upper bound for each pair of elements).
TESTS:
sage: J = JoinSemilattice([[1,2],[3],[3]]) sage: TestSuite(J).run()
sage: P = Poset([[1,2],[3],[3]]) sage: J = JoinSemilattice(P) sage: TestSuite(J).run()
-
Element
¶ alias of
JoinSemilatticeElement
-
join
(x, y=None)¶ Return the join of given elements in the lattice.
INPUT:
x, y
- two elements of the (semi)lattice 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
Test that this method also works for facade lattices:
sage: L = LatticePoset([[1,2],[3],[3]], facade = True) sage: L.join(1, 0) 1 sage: L.join(1, 2) 3
-
join_matrix
()¶ Return a matrix whose
(i,j)
entry 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
-
complements
(element=None)¶ Return the list of complements of an element in the lattice, or the dictionary of complements for all elements.
Elements
and
are complements if their meet and join are respectively the bottom and the top element of the lattice.
INPUT:
element
- an element of the poset whose complement is returned. 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
and
are complements of each other:
sage: 'a' in C['b'] True sage: 'b' in C['a'] True
Full list of complements:
sage: L.complements() # random {0: [1], 1: [0], 'a': ['b', 'c'], 'b': ['c', 'a'], 'c': ['b', 'a']} sage: L=LatticePoset({0:[1,2],1:[3],2:[3],3:[4]}) sage: L.complements() # random {0: [4], 4: [0]} sage: L.complements(1) []
TESTS:
sage: L=LatticePoset({0:['a','b','c'], 'a':[1], 'b':[1], 'c':[1]}) sage: for v,v_complements in L.complements().items(): ....: for v_c in v_complements: ....: assert L.meet(v,v_c) == L.bottom() ....: assert L.join(v,v_c) == L.top()
-
is_atomic
()¶ Returns
True
ifself
is an atomic lattice andFalse
otherwise.A lattice is atomic if every element can be written as a join of atoms.
EXAMPLES:
sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]}) sage: L.is_atomic() True sage: L = LatticePoset({0:[1,2],1:[3],2:[3],3:[4]}) sage: L.is_atomic() False
NOTES:
See [Sta97], Section 3.3 for a discussion of atomic lattices.
REFERENCES:
[Sta97] Stanley, Richard. Enumerative Combinatorics, Vol. 1. Cambridge University Press, 1997
-
is_complemented
()¶ Returns
True
ifself
is a complemented lattice, andFalse
otherwise.EXAMPLES:
sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]}) sage: L.is_complemented() True sage: L = LatticePoset({0:[1,2],1:[3],2:[3],3:[4]}) sage: L.is_complemented() False
-
is_distributive
()¶ Return
True
if the lattice is distributive, andFalse
otherwise.A lattice
is distributive if meet distributes over join:
for every
just like
in normal arithmetic. For duality in lattices it follows that then also join distributes over meet.
EXAMPLES:
sage: L = LatticePoset({0:[1,2],1:[3],2:[3]}) sage: L.is_distributive() True sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]}) sage: L.is_distributive() False
-
is_lower_semimodular
()¶ Return
True
if the lattice is lower semimodular andFalse
otherwise.A lattice is lower semimodular if for any
in the poset that covers
and
, both
and
cover their meet.
See also
is_modular()
andis_upper_semimodular()
.See Wikipedia article Semimodular_lattice
EXAMPLES:
sage: L = posets.DiamondPoset(5) sage: L.is_lower_semimodular() True sage: L = posets.PentagonPoset() sage: L.is_lower_semimodular() False sage: L = posets.ChainPoset(6) sage: L.is_lower_semimodular() True
ALGORITHM:
Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1].
-
is_modular
(L=None)¶ Return
True
if the lattice is modular 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
in a lattice
is modular if
implies
for every
. We say
is modular if
is modular for all
. 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
in a lattice
is modular if
implies
for every
.
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_supersolvable
()¶ Return
True
ifself
is a supersolvable lattice andFalse
otherwise.A lattice
is supersolvable if there exists a maximal chain
such that every
is a modular element in
.
EXAMPLES:
sage: L = posets.DiamondPoset(5) sage: L.is_supersolvable() True sage: L = posets.PentagonPoset() sage: L.is_supersolvable() False sage: L = posets.ChainPoset(6) sage: L.is_supersolvable() True sage: L = LatticePoset({1:[2,3],2:[4,5],3:[5,6],4:[7],5:[7],6:[7]}) sage: L.is_supersolvable() True sage: L.is_modular() False sage: L = LatticePoset({0: [1, 2, 3, 4], 1: [5, 6, 7], ....: 2: [5, 8, 9], 3: [6, 8, 10], 4: [7, 9, 10], ....: 5: [11], 6: [11], 7: [11], 8: [11], ....: 9: [11], 10: [11]}) sage: L.is_supersolvable() False
-
is_upper_semimodular
()¶ Return
True
if the lattice is upper semimodular andFalse
otherwise.A lattice is upper semimodular if for any
in the poset that is covered by
and
, both
and
are covered by their join.
See also
is_modular()
andis_lower_semimodular()
.See Wikipedia article Semimodular_lattice
EXAMPLES:
sage: L = posets.DiamondPoset(5) sage: L.is_upper_semimodular() True sage: L = posets.PentagonPoset() sage: L.is_upper_semimodular() False sage: L = posets.ChainPoset(6) sage: L.is_upper_semimodular() True sage: L = LatticePoset(posets.IntegerPartitions(4)) sage: L.is_upper_semimodular() True
ALGORITHM:
Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1].
-
sublattice
(elms)¶ Return the smallest sublattice containing elements on the given list.
INPUT:
elms
– a list of elements of the lattice.
EXAMPLES:
sage: L=LatticePoset(( [], [[1,2],[1,17],[1,8],[2,3],[2,22],[2,5],[2,7],[17,22],[17,13],[8,7],[8,13],[3,16],[3,9],[22,16],[22,18],[22,10],[5,18],[5,14],[7,9],[7,14],[7,10],[13,10],[16,6],[16,19],[9,19],[18,6],[18,33],[14,33],[10,19],[10,33],[6,4],[19,4],[33,4]] )) sage: L.sublattice([14, 13, 22]).list() [1, 2, 8, 7, 14, 17, 13, 22, 10, 33] sage: L = Posets.BooleanLattice(3) sage: L.sublattice([3,5,6,7]) Finite lattice containing 8 elements
Note
This is very unoptimal algorithm. Better one is described on “Computing the sublattice of a lattice generated by a set of elements” by K. Bertet and M. Morvan. Feel free to implement it.
-
-
class
sage.combinat.posets.lattices.
FiniteMeetSemilattice
(hasse_diagram, elements, category, facade, key)¶ Bases:
sage.combinat.posets.posets.FinitePoset
Note
We assume that the argument passed to MeetSemilattice is the poset of a meet-semilattice (i.e. a poset with greatest lower bound for each pair of elements).
TESTS:
sage: M = MeetSemilattice([[1,2],[3],[3]]) sage: TestSuite(M).run()
sage: P = Poset([[1,2],[3],[3]]) sage: M = MeetSemilattice(P) sage: TestSuite(M).run()
-
Element
¶ alias of
MeetSemilatticeElement
-
meet
(x, y=None)¶ Return the meet of given elements in the lattice.
EXAMPLES:
sage: D = Posets.DiamondPoset(5) sage: D.meet(1, 2) 0 sage: D.meet(1, 1) 1 sage: D.meet(1, 0) 0 sage: D.meet(1, 4) 1
Using list of elements as an argument. Meet of empty list is the bottom element:
sage: B4=Posets.BooleanLattice(4) sage: B4.meet([3,5,6]) 0 sage: B4.meet([]) 15
Test that this method also works for facade lattices:
sage: L = LatticePoset([[1,2],[3],[3]], facade = True) sage: L.meet(2, 3) 2 sage: L.meet(1, 2) 0
-
meet_matrix
()¶ Return a matrix whose
(i,j)
entry 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
-
-
sage.combinat.posets.lattices.
JoinSemilattice
(data, *args, **options)¶ Construct a join semi-lattice from various forms of input data.
INPUT:
data
,*args
,**options
– data and options that will be passed down 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: elms = [1,2,3,4,5,6,7] sage: rels = [[1,2],[3,4],[4,5],[2,5]] sage: JoinSemilattice((elms, rels)) Traceback (most recent call last): ... ValueError: Not a join semilattice.
-
sage.combinat.posets.lattices.
LatticePoset
(data, *args, **options)¶ Construct a lattice from various forms of input data.
INPUT:
data
,*args
,**options
– data and options that will be passed down toPoset()
to construct a poset that is also a lattice.
OUTPUT:
FiniteLatticePoset – an instance ofFiniteLatticePoset
See also
Posets
,FiniteLatticePosets
,JoinSemiLattice()
,MeetSemiLattice()
EXAMPLES:
Using data that defines a poset:
sage: LatticePoset([[1,2],[3],[3]]) Finite lattice containing 4 elements sage: LatticePoset([[1,2],[3],[3]], cover_relations = True) Finite lattice containing 4 elements
Using a previously constructed poset:
sage: P = Poset([[1,2],[3],[3]]) sage: L = LatticePoset(P); L Finite lattice containing 4 elements sage: type(L) <class 'sage.combinat.posets.lattices.FiniteLatticePoset_with_category'>
If the data is not a lattice, then an error is raised:
sage: elms = [1,2,3,4,5,6,7] sage: rels = [[1,2],[3,4],[4,5],[2,5]] sage: LatticePoset((elms, rels)) Traceback (most recent call last): ... ValueError: Not a lattice.
Creating a facade lattice:
sage: L = LatticePoset([[1,2],[3],[3]], facade = True) sage: L.category() Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets sage: parent(L[0]) Integer Ring sage: TestSuite(L).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented
-
sage.combinat.posets.lattices.
MeetSemilattice
(data, *args, **options)¶ Construct a meet semi-lattice from various forms of input data.
INPUT:
data
,*args
,**options
– data and options that will be passed down 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: elms = [1,2,3,4,5,6,7] sage: rels = [[1,2],[3,4],[4,5],[2,5]] sage: MeetSemilattice((elms, rels)) Traceback (most recent call last): ... ValueError: Not a meet semilattice.