Finite semilattices and lattices¶

class sage.combinat.posets.lattices.FiniteJoinSemilattice(hasse_diagram, elements, category, facade, key)

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 OR
• x - 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 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)

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.

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.

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.

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)

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

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.


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

Hasse diagrams of posets

Next topic

Linear Extensions of Posets