Lattice posets

class sage.categories.lattice_posets.DistributiveLattices(base_category)[source]

Bases: CategoryWithAxiom

The category of distributive lattices.

EXAMPLES:

sage: cat = FiniteLatticePosets().Distributive(); cat
Category of finite distributive lattices

sage: cat.super_categories()
[Category of finite lattice posets,
 Category of distributive lattices]

>>> from sage.all import *
>>> cat = FiniteLatticePosets().Distributive(); cat
Category of finite distributive lattices

>>> cat.super_categories()
[Category of finite lattice posets,
 Category of distributive lattices]
class Finite(base_category)[source]

Bases: CategoryWithAxiom

class ParentMethods[source]

Bases: object

is_distributive()[source]

Return whether self is a distributive lattice.

EXAMPLES:

sage: P = posets.Crown(4).order_ideals_lattice()
sage: P.is_distributive()
True

>>> from sage.all import *
>>> P = posets.Crown(Integer(4)).order_ideals_lattice()
>>> P.is_distributive()
True
extra_super_categories()[source]

Return a list of the super categories of self.

These encode implications between properties.

EXAMPLES:

sage: LatticePosets().Distributive().super_categories()
[Category of congruence uniform lattice posets,
 Category of trim lattice posets,
 Category of chain graded lattice posets]

>>> from sage.all import *
>>> LatticePosets().Distributive().super_categories()
[Category of congruence uniform lattice posets,
 Category of trim lattice posets,
 Category of chain graded lattice posets]
class sage.categories.lattice_posets.LatticePosets[source]

Bases: Category

The category of lattices, i.e. partially ordered sets in which any two elements have a unique supremum (the elements’ least upper bound; called their join) and a unique infimum (greatest lower bound; called their meet).

EXAMPLES:

sage: LatticePosets()
Category of lattice posets
sage: LatticePosets().super_categories()
[Category of posets]
sage: LatticePosets().example()
NotImplemented

>>> from sage.all import *
>>> LatticePosets()
Category of lattice posets
>>> LatticePosets().super_categories()
[Category of posets]
>>> LatticePosets().example()
NotImplemented

See also

class ChainGraded(base_category)[source]

Bases: CategoryWithAxiom

The category of graded lattices.

EXAMPLES:

sage: cat = FiniteLatticePosets().ChainGraded(); cat
Category of finite chain graded lattice posets

sage: cat.super_categories()
[Category of finite lattice posets,
 Category of chain graded lattice posets]

>>> from sage.all import *
>>> cat = FiniteLatticePosets().ChainGraded(); cat
Category of finite chain graded lattice posets

>>> cat.super_categories()
[Category of finite lattice posets,
 Category of chain graded lattice posets]
class ParentMethods[source]

Bases: object

is_graded()[source]

Return whether self is a graded lattice.

EXAMPLES:

sage: posets.DivisorLattice(12).is_graded()
True

>>> from sage.all import *
>>> posets.DivisorLattice(Integer(12)).is_graded()
True
class CongruenceUniform(base_category)[source]

Bases: CategoryWithAxiom

The category of congruence uniform lattices.

EXAMPLES:

sage: cat = FiniteLatticePosets().CongruenceUniform(); cat
Category of finite congruence uniform lattice posets
sage: cat.super_categories()
[Category of finite lattice posets,
 Category of congruence uniform lattice posets]

>>> from sage.all import *
>>> cat = FiniteLatticePosets().CongruenceUniform(); cat
Category of finite congruence uniform lattice posets
>>> cat.super_categories()
[Category of finite lattice posets,
 Category of congruence uniform lattice posets]
class ParentMethods[source]

Bases: object

is_congruence_uniform()[source]

Return whether self is a congruence uniform lattice.

EXAMPLES:

sage: posets.TamariLattice(4).is_congruence_uniform()
True

>>> from sage.all import *
>>> posets.TamariLattice(Integer(4)).is_congruence_uniform()
True
extra_super_categories()[source]

Return a list of the super categories of self.

These encode implications between properties.

EXAMPLES:

sage: FiniteLatticePosets().CongruenceUniform().super_categories()
[Category of finite lattice posets,
 Category of congruence uniform lattice posets]

>>> from sage.all import *
>>> FiniteLatticePosets().CongruenceUniform().super_categories()
[Category of finite lattice posets,
 Category of congruence uniform lattice posets]
class Extremal(base_category)[source]

Bases: CategoryWithAxiom

The category of extremal uniform lattices.

EXAMPLES:

sage: cat = FiniteLatticePosets().Extremal(); cat
Category of finite extremal lattice posets

sage: cat.super_categories()
[Category of finite lattice posets,
 Category of extremal lattice posets]

>>> from sage.all import *
>>> cat = FiniteLatticePosets().Extremal(); cat
Category of finite extremal lattice posets

>>> cat.super_categories()
[Category of finite lattice posets,
 Category of extremal lattice posets]
class ParentMethods[source]

Bases: object

is_extremal()[source]

Return whether self is an extremal lattice.

EXAMPLES:

sage: posets.TamariLattice(4).is_extremal()
True

>>> from sage.all import *
>>> posets.TamariLattice(Integer(4)).is_extremal()
True
Finite[source]

alias of FiniteLatticePosets

class ParentMethods[source]

Bases: object

join(x, y)[source]

Return the join of \(x\) and \(y\) in this lattice.

INPUT:

  • x, y – elements of self

EXAMPLES:

sage: D = LatticePoset((divisors(60), attrcall("divides")))             # needs sage.graphs sage.modules
sage: D.join( D(6), D(10) )                                             # needs sage.graphs sage.modules
30

>>> from sage.all import *
>>> D = LatticePoset((divisors(Integer(60)), attrcall("divides")))             # needs sage.graphs sage.modules
>>> D.join( D(Integer(6)), D(Integer(10)) )                                             # needs sage.graphs sage.modules
30
meet(x, y)[source]

Return the meet of \(x\) and \(y\) in this lattice.

INPUT:

  • x, y – elements of self

EXAMPLES:

sage: D = LatticePoset((divisors(30), attrcall("divides")))             # needs sage.graphs sage.modules
sage: D.meet( D(6), D(15) )                                             # needs sage.graphs sage.modules
3

>>> from sage.all import *
>>> D = LatticePoset((divisors(Integer(30)), attrcall("divides")))             # needs sage.graphs sage.modules
>>> D.meet( D(Integer(6)), D(Integer(15)) )                                             # needs sage.graphs sage.modules
3
class Semidistributive(base_category)[source]

Bases: CategoryWithAxiom

The category of semidistributive lattices.

EXAMPLES:

sage: cat = FiniteLatticePosets().Semidistributive(); cat
Category of finite semidistributive lattice posets

sage: cat.super_categories()
[Category of finite lattice posets,
 Category of semidistributive lattice posets]

>>> from sage.all import *
>>> cat = FiniteLatticePosets().Semidistributive(); cat
Category of finite semidistributive lattice posets

>>> cat.super_categories()
[Category of finite lattice posets,
 Category of semidistributive lattice posets]
class ParentMethods[source]

Bases: object

is_semidistributive()[source]

Return whether self is a semidistributive lattice.

EXAMPLES:

sage: posets.TamariLattice(4).is_semidistributive()
True

>>> from sage.all import *
>>> posets.TamariLattice(Integer(4)).is_semidistributive()
True
kappa(a)[source]

Return the maximum element greater than the element covered by a but not greater than a.

Define \(\kappa(a)\) as the maximum element of \((\uparrow a_*) \setminus (\uparrow a)\), where \(a_*\) is the element covered by \(a\). It is always a meet-irreducible element, if it exists.

INPUT:

  • a – a join-irreducible element of the lattice

Warning

Element a is expected to be join-irreducible, and this is not checked.

OUTPUT:

the element \(\kappa(a)\)

This will raise a ValueError if there is not a unique greatest element with given constraints.

EXAMPLES:

sage: V = ['b', 0, 1, 2, 3, 4, 't']
sage: C = [['b', 0], ['b', 1], [0, 2], [2, 3], [2, 4], [3, 't'], [1, 4], [4, 't']]
sage: L = LatticePoset([V, C], category=LatticePosets().Finite().Semidistributive())
sage: [(a, L.kappa(a)) for a in L.join_irreducibles()]
[(0, 1), (2, 0), (3, 4), (1, 3)]

>>> from sage.all import *
>>> V = ['b', Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), 't']
>>> C = [['b', Integer(0)], ['b', Integer(1)], [Integer(0), Integer(2)], [Integer(2), Integer(3)], [Integer(2), Integer(4)], [Integer(3), 't'], [Integer(1), Integer(4)], [Integer(4), 't']]
>>> L = LatticePoset([V, C], category=LatticePosets().Finite().Semidistributive())
>>> [(a, L.kappa(a)) for a in L.join_irreducibles()]
[(0, 1), (2, 0), (3, 4), (1, 3)]
kappa_dual(a)[source]

Return the minimum element smaller than the element covering a but not smaller than a.

Define \(\kappa^*(a)\) as the minimum element of \((\downarrow a_*) \setminus (\downarrow a)\), where \(a_*\) is the element covering \(a\). It is always a join-irreducible element, if it exists.

INPUT:

  • a – a meet-irreducible element of the lattice

Warning

Element a is expected to be meet-irreducible, and this is not checked.

OUTPUT:

the element \(\kappa^*(a)\)

This will raise a ValueError if there is not a unique greatest element with given constraints.

EXAMPLES:

sage: V = ['b', 0, 1, 2, 3, 4, 't']
sage: C = [['b', 0], ['b', 1], [0, 2], [2, 3], [2, 4], [3, 't'], [1, 4], [4, 't']]
sage: L = LatticePoset([V, C], category=LatticePosets().Finite().Semidistributive())
sage: [(a, L.kappa_dual(a)) for a in L.meet_irreducibles()]
[(0, 2), (3, 1), (1, 0), (4, 3)]

>>> from sage.all import *
>>> V = ['b', Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), 't']
>>> C = [['b', Integer(0)], ['b', Integer(1)], [Integer(0), Integer(2)], [Integer(2), Integer(3)], [Integer(2), Integer(4)], [Integer(3), 't'], [Integer(1), Integer(4)], [Integer(4), 't']]
>>> L = LatticePoset([V, C], category=LatticePosets().Finite().Semidistributive())
>>> [(a, L.kappa_dual(a)) for a in L.meet_irreducibles()]
[(0, 2), (3, 1), (1, 0), (4, 3)]
rowmotion_semidistributive(a)[source]

Return the image of the element a under semidistributive rowmotion in self.

Classical rowmotion is usually defined as an automorphism on the set of order ideals \(J(P)\) of a finite poset \(P\). It is a special case of semidistributive rowmotion because every distributive lattice is isomorphic to \(J(P)\) for some \(P\) by Birkhoff’s representation theorem.

See also

If the image of rowmotion of several elements is needed, semidistributive_rowmotion is much more efficient.

EXAMPLES:

sage: V = ['b', 0, 1, 2, 3, 4, 't']
sage: C = [['b', 0], ['b', 1], [0, 2], [2, 3], [2, 4], [3, 't'], [1, 4], [4, 't']]
sage: L = LatticePoset([V, C], category=LatticePosets().Finite().Semidistributive())
sage: L.rowmotion_semidistributive(0)
2

sage: L = posets.TamariLattice(3)
sage: row = L.rowmotion_semidistributive
sage: DS = DiscreteDynamicalSystem(L, row)
sage: sorted([sorted([DyckWord(x[:-1]) for x in c]) for c in DS.cycles()])
[[[1, 0, 1, 0, 1, 0], [1, 1, 1, 0, 0, 0]],
 [[1, 0, 1, 1, 0, 0], [1, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 0]]]
sage: L = posets.TamariLattice(4)
sage: L.rowmotion_semidistributive((1,1,0,1,1,0,0,0,0))
(1, 0, 1, 1, 0, 0, 1, 0, 0)

>>> from sage.all import *
>>> V = ['b', Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), 't']
>>> C = [['b', Integer(0)], ['b', Integer(1)], [Integer(0), Integer(2)], [Integer(2), Integer(3)], [Integer(2), Integer(4)], [Integer(3), 't'], [Integer(1), Integer(4)], [Integer(4), 't']]
>>> L = LatticePoset([V, C], category=LatticePosets().Finite().Semidistributive())
>>> L.rowmotion_semidistributive(Integer(0))
2

>>> L = posets.TamariLattice(Integer(3))
>>> row = L.rowmotion_semidistributive
>>> DS = DiscreteDynamicalSystem(L, row)
>>> sorted([sorted([DyckWord(x[:-Integer(1)]) for x in c]) for c in DS.cycles()])
[[[1, 0, 1, 0, 1, 0], [1, 1, 1, 0, 0, 0]],
 [[1, 0, 1, 1, 0, 0], [1, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 0]]]
>>> L = posets.TamariLattice(Integer(4))
>>> L.rowmotion_semidistributive((Integer(1),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)))
(1, 0, 1, 1, 0, 0, 1, 0, 0)

Check that classical rowmotion is a special case of semidistributive rowmotion:

sage: T = posets.TamariLattice(3)
sage: L = T.order_ideals_lattice()
sage: all(L.rowmotion_semidistributive(a) == T.rowmotion(a) for a in L)
True

sage: P = posets.UpDownPoset(10)
sage: L = T.order_ideals_lattice()
sage: all(L.rowmotion_semidistributive(a) == T.rowmotion(a) for a in L)
True
[Python] 
>>> from sage.all import *
>>> T = posets.TamariLattice(Integer(3))
>>> L = T.order_ideals_lattice()
>>> all(L.rowmotion_semidistributive(a) == T.rowmotion(a) for a in L)
True

>>> P = posets.UpDownPoset(Integer(10))
>>> L = T.order_ideals_lattice()
>>> all(L.rowmotion_semidistributive(a) == T.rowmotion(a) for a in L)
True
spine()[source]

Return the spine of self.

For a semidistributive lattice \(L\), the spine of \(L\) is the distributive lattice constructed as the subposet on the union of longest maximal chains.

EXAMPLES:

sage: P = posets.TamariLattice(4)
sage: S = P.spine(); S
Finite lattice containing 8 elements
sage: S.category()
Category of facade finite enumerated distributive lattices

>>> from sage.all import *
>>> P = posets.TamariLattice(Integer(4))
>>> S = P.spine(); S
Finite lattice containing 8 elements
>>> S.category()
Category of facade finite enumerated distributive lattices
class Stone(base_category)[source]

Bases: CategoryWithAxiom

The category of Stone lattices.

EXAMPLES:

sage: cat = FiniteLatticePosets().Stone(); cat
Category of finite stone distributive lattices

sage: cat.super_categories()
[Category of finite distributive lattices,
 Category of stone lattice posets]

>>> from sage.all import *
>>> cat = FiniteLatticePosets().Stone(); cat
Category of finite stone distributive lattices

>>> cat.super_categories()
[Category of finite distributive lattices,
 Category of stone lattice posets]
class ParentMethods[source]

Bases: object

is_stone()[source]

Return whether self is a Stone lattice.

EXAMPLES:

sage: posets.DivisorLattice(12).is_stone()
True

>>> from sage.all import *
>>> posets.DivisorLattice(Integer(12)).is_stone()
True
extra_super_categories()[source]

Return a list of the super categories of self.

These encode implications between properties.

EXAMPLES:

sage: FiniteLatticePosets().Stone().super_categories()
[Category of finite distributive lattices,
 Category of stone lattice posets]

>>> from sage.all import *
>>> FiniteLatticePosets().Stone().super_categories()
[Category of finite distributive lattices,
 Category of stone lattice posets]
class SubcategoryMethods[source]

Bases: object

ChainGraded()[source]

A lattice is graded if all maximal chains have the same length.

To avoid possible confusion, the name of the axiom is ChainGraded.

EXAMPLES:

sage: P = posets.DivisorLattice(24)
sage: P in FiniteLatticePosets().ChainGraded()
True

>>> from sage.all import *
>>> P = posets.DivisorLattice(Integer(24))
>>> P in FiniteLatticePosets().ChainGraded()
True
CongruenceUniform()[source]

A finite lattice \((L, \vee, \wedge)\) is congruence uniform if it can be constructed by a sequence of interval doublings starting with the lattice with one element.

EXAMPLES:

sage: P = posets.TamariLattice(2)
sage: P in FiniteLatticePosets().CongruenceUniform()
True

>>> from sage.all import *
>>> P = posets.TamariLattice(Integer(2))
>>> P in FiniteLatticePosets().CongruenceUniform()
True
Distributive()[source]

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

From duality in lattices, it follows that then also join distributes over meet.

A distributive lattice is always graded.

See Wikipedia article Distributive lattice.

EXAMPLES:

sage: P = posets.ChainPoset(2).order_ideals_lattice()
sage: P in FiniteLatticePosets().Distributive()
True

>>> from sage.all import *
>>> P = posets.ChainPoset(Integer(2)).order_ideals_lattice()
>>> P in FiniteLatticePosets().Distributive()
True
Extremal()[source]

A finite lattice \((L, \vee, \wedge)\) is extremal if if it has a chain of length \(n\) (containing \(n+1\) elements) and exactly \(n\) join-irreducibles and \(n\) meet-irreducibles.

This notion was defined by George Markowsky.

EXAMPLES:

sage: P = posets.TamariLattice(2)
sage: P in FiniteLatticePosets().Extremal()
True

>>> from sage.all import *
>>> P = posets.TamariLattice(Integer(2))
>>> P in FiniteLatticePosets().Extremal()
True
Semidistributive()[source]

A finite lattice \((L, \vee, \wedge)\) is semidistributive if it is both join-semidistributive and meet-semidistributive.

A finite lattice is join-semidistributive if for all elements \(e, x, y\) in the lattice we have

\[e \vee x = e \vee y \implies e \vee x = e \vee (x \wedge y)\]

Meet-semidistributivity is the dual property.

EXAMPLES:

sage: P = posets.TamariLattice(2)
sage: P in FiniteLatticePosets().Semidistributive()
True

>>> from sage.all import *
>>> P = posets.TamariLattice(Integer(2))
>>> P in FiniteLatticePosets().Semidistributive()
True
Stone()[source]

A Stone lattice \((L, \vee, \wedge)\) is a pseudo-complemented distributive lattice such that \(a^* \vee a^{**} = 1\).

See Wikipedia article Stone algebra.

EXAMPLES:

sage: P = posets.DivisorLattice(24)
sage: P in FiniteLatticePosets().Stone()
True

>>> from sage.all import *
>>> P = posets.DivisorLattice(Integer(24))
>>> P in FiniteLatticePosets().Stone()
True
Trim()[source]

A finite lattice \((L, \vee, \wedge)\) is trim if it is extremal and left modular.

This notion is defined in [Thom2006].

EXAMPLES:

sage: P = posets.TamariLattice(2)
sage: P in FiniteLatticePosets().Trim()
True

>>> from sage.all import *
>>> P = posets.TamariLattice(Integer(2))
>>> P in FiniteLatticePosets().Trim()
True
class Trim(base_category)[source]

Bases: CategoryWithAxiom

The category of trim uniform lattices.

EXAMPLES:

sage: cat = FiniteLatticePosets().Trim(); cat
Category of finite trim lattice posets
sage: cat.super_categories()
[Category of finite lattice posets,
 Category of trim lattice posets]

>>> from sage.all import *
>>> cat = FiniteLatticePosets().Trim(); cat
Category of finite trim lattice posets
>>> cat.super_categories()
[Category of finite lattice posets,
 Category of trim lattice posets]
ChainGraded[source]

alias of DistributiveLattices

class ParentMethods[source]

Bases: object

is_trim()[source]

Return whether self is a trim lattice.

EXAMPLES:

sage: posets.TamariLattice(4).is_trim()
True

>>> from sage.all import *
>>> posets.TamariLattice(Integer(4)).is_trim()
True
extra_super_categories()[source]

Return a list of the super categories of self.

These encode implications between properties.

EXAMPLES:

sage: FiniteLatticePosets().Trim().super_categories()
[Category of finite lattice posets,
 Category of trim lattice posets]

>>> from sage.all import *
>>> FiniteLatticePosets().Trim().super_categories()
[Category of finite lattice posets,
 Category of trim lattice posets]
super_categories()[source]

Return a list of the (immediate) super categories of self, as per Category.super_categories().

EXAMPLES:

sage: LatticePosets().super_categories()
[Category of posets]

>>> from sage.all import *
>>> LatticePosets().super_categories()
[Category of posets]