Finite semilattices and lattices

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)

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
join_matrix()

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
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 \(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 poset whose complement is returned. If None (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()
is_atomic()

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
is_complemented()

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
is_distributive()

Return True if the lattice is distributive, and False 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_lower_semimodular()

Return True if the lattice is lower semimodular and False otherwise.

A lattice is lower semimodular if for any \(x\) in the poset that covers \(y\) and \(z\), both \(y\) and \(z\) 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].

is_modular()

Return True if the lattice is modular and False otherwise.

A lattice is modular if \(x \le b\) implies \(x \vee (a \wedge b)= (x \vee a) \wedge b\) for every \(a\) and \(b\). 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].

is_upper_semimodular()

Return True if the lattice is upper semimodular and False otherwise.

A lattice is upper semimodular if for any \(x\) in the poset that is covered by \(y\) and \(z\), both \(y\) and \(z\) 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].

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)

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
meet_matrix()

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
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 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 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 to Poset() to construct a poset that is also a lattice.

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

Previous topic

Elements of posets, lattices, semilattices, etc.

Next topic

Linear Extensions of Posets

This Page