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)

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

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

Returns all elements in self that have a complement.

A complement of x is an element y such that the meet of x and y is the bottom element of self and the join of x and y is the top element of self.

EXAMPLES:

sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]})
sage: L.complements()
[4, 3, 3, 2, 0]

sage: L = LatticePoset({0:[1,2],1:[3],2:[3],3:[4]})
sage: L.complements()
[4, None, None, None, 0]

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

Returns True if the lattice is distributive, and False otherwise.

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

Return True if self is a lower semimodular lattice 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

is_modular(L)

Return True if self is a modular lattice and False otherwise.

A lattice is modular if it is both upper semimodular and 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

is_upper_semimodular(L)

Return True if self is an upper semimodular lattice 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

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)

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

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()
Category of facade finite 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, *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