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()
alias of JoinSemilatticeElement
Return the join of two elements in the lattice.
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
If this method is used directly, it is not necessary to coerce elements into the poset. (Trac #11292)
sage: D = Posets.DiamondPoset(5)
sage: D.join(1, 0)
1
sage: D.join(1, 4)
4
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
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
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()
alias of LatticePosetElement
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:
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()
Returns True if self is an atomic lattice and False 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 |
Returns True if self is a complemented lattice, and False 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
Return True if the lattice is distributive, and False 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
Return True if the lattice is lower semimodular and False otherwise.
A lattice is lower semimodular if for any in the poset that covers
and
, both
and
cover their meet.
See also is_modular() and is_upper_semimodular().
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].
Return True if the lattice is modular and False otherwise.
A lattice is modular if implies
for every
and
. There are other equivalent
definitions, see Wikipedia article Modular_lattice.
See also is_upper_semimodular() and is_lower_semimodular().
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
ALGORITHM:
Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1].
Return True if the lattice is upper semimodular and False 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() and is_lower_semimodular().
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].
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()
alias of MeetSemilatticeElement
Return the meet of two 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
If this method is used directly, it is not necessary to coerce elements into the poset. (Trac #11292)
sage: D = Posets.DiamondPoset(5)
sage: D.meet(1, 0)
0
sage: D.meet(1, 4)
1
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
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
Construct a join semi-lattice from various forms of input data.
INPUT:
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.
Construct a lattice from various forms of input data.
INPUT:
OUTPUT:
FiniteLatticePoset – 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 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
Construct a meet semi-lattice from various forms of input data.
INPUT:
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.