Generalized Tamari lattices

These lattices depend on three parameters \(a\), \(b\) and \(m\), where \(a\) and \(b\) are coprime positive integers and \(m\) is a nonnegative integer.

The elements are Dyck paths in the \((a \times b)\)-rectangle. The order relation depends on \(m\).

To use the provided functionality, you should import Generalized Tamari lattices by typing:

sage: from sage.combinat.tamari_lattices import GeneralizedTamariLattice

Then,

sage: GeneralizedTamariLattice(3,2)
Finite lattice containing 2 elements
sage: GeneralizedTamariLattice(4,3)
Finite lattice containing 5 elements

The classical Tamari lattices are special cases of this construction and are also available directly using the catalogue of posets, as follows:

sage: posets.TamariLattice(3)
Finite lattice containing 5 elements

See also

For more detailed information see TamariLattice(), GeneralizedTamariLattice().

sage.combinat.tamari_lattices.DexterSemilattice(n)

Return the \(n\)-th Dexter meet-semilattice.

INPUT:

  • n – a nonnegative integer (the index)

OUTPUT:

a finite meet-semilattice

The elements of the semilattice are Dyck paths in the \((n+1 \times n)\)-rectangle.

EXAMPLES:

sage: posets.DexterSemilattice(3)
Finite meet-semilattice containing 5 elements

sage: P = posets.DexterSemilattice(4); P
Finite meet-semilattice containing 14 elements
sage: len(P.maximal_chains())
15
sage: len(P.maximal_elements())
4
sage: P.chain_polynomial()
q^5 + 19*q^4 + 47*q^3 + 42*q^2 + 14*q + 1

REFERENCES:

sage.combinat.tamari_lattices.GeneralizedTamariLattice(a, b, m=1, check=True)

Return the \((a,b)\)-Tamari lattice of parameter \(m\).

INPUT:

  • \(a\) and \(b\) – coprime integers with \(a \geq b\)

  • \(m\) – a nonnegative integer such that \(a \geq b m\)

OUTPUT:

  • a finite lattice (the lattice property is only conjectural in general)

The elements of the lattice are Dyck paths in the \((a \times b)\)-rectangle.

The parameter \(m\) (slope) is used only to define the covering relations. When the slope \(m\) is \(0\), two paths are comparable if and only if one is always above the other.

The usual Tamari lattice of index \(b\) is the special case \(a=b+1\) and \(m=1\).

Other special cases give the \(m\)-Tamari lattices studied in [BMFPR].

EXAMPLES:

sage: from sage.combinat.tamari_lattices import GeneralizedTamariLattice
sage: GeneralizedTamariLattice(3,2)
Finite lattice containing 2 elements
sage: GeneralizedTamariLattice(4,3)
Finite lattice containing 5 elements
sage: GeneralizedTamariLattice(4,4)
Traceback (most recent call last):
...
ValueError: the numbers a and b must be coprime with a>=b
sage: GeneralizedTamariLattice(7,5,2)
Traceback (most recent call last):
...
ValueError: the condition a>=b*m does not hold
sage: P = GeneralizedTamariLattice(5,3);P
Finite lattice containing 7 elements

REFERENCES:

BMFPR(1,2)

M. Bousquet-Melou, E. Fusy, L.-F. Preville Ratelle. The number of intervals in the m-Tamari lattices. arXiv 1106.1498

sage.combinat.tamari_lattices.TamariLattice(n, m=1)

Return the \(n\)-th Tamari lattice.

Using the slope parameter \(m\), one can also get the \(m\)-Tamari lattices.

INPUT:

  • \(n\) – a nonnegative integer (the index)

  • \(m\) – an optional nonnegative integer (the slope, default to 1)

OUTPUT:

a finite lattice

In the usual case, the elements of the lattice are Dyck paths in the \((n+1 \times n)\)-rectangle. For a general slope \(m\), the elements are Dyck paths in the \((m n+1 \times n)\)-rectangle.

See Tamari lattice for mathematical background.

EXAMPLES:

sage: posets.TamariLattice(3)
Finite lattice containing 5 elements

sage: posets.TamariLattice(3, 2)
Finite lattice containing 12 elements

REFERENCES:

sage.combinat.tamari_lattices.paths_in_triangle(i, j, a, b)

Return all Dyck paths from \((0,0)\) to \((i,j)\) in the \((a \times b)\)-rectangle.

This means that at each step of the path, one has \(a y \geq b x\).

A path is represented by a sequence of \(0\) and \(1\), where \(0\) is an horizontal step \((1,0)\) and \(1\) is a vertical step \((0,1)\).

INPUT:

  • \(a\) and \(b\) – coprime integers with \(a \geq b\)

  • \(i\) and \(j\) – nonnegative integers with \(1 \geq \frac{j}{b} \geq \frac{bi}{a} \geq 0\)

OUTPUT:

  • a list of paths

EXAMPLES:

sage: from sage.combinat.tamari_lattices import paths_in_triangle
sage: paths_in_triangle(2,2,2,2)
[(1, 0, 1, 0), (1, 1, 0, 0)]
sage: paths_in_triangle(2,3,4,4)
[(1, 0, 1, 0, 1), (1, 1, 0, 0, 1), (1, 0, 1, 1, 0),
(1, 1, 0, 1, 0), (1, 1, 1, 0, 0)]
sage: paths_in_triangle(2,1,4,4)
Traceback (most recent call last):
...
ValueError: the endpoint is not valid
sage: paths_in_triangle(3,2,5,3)
[(1, 0, 1, 0, 0), (1, 1, 0, 0, 0)]
sage.combinat.tamari_lattices.swap(p, i, m=1)

Perform a covering move in the \((a,b)\)-Tamari lattice of parameter \(m\).

The letter at position \(i\) in \(p\) must be a \(0\), followed by at least one \(1\).

INPUT:

  • p – a Dyck path in the \((a \times b)\)-rectangle

  • i – an integer between \(0\) and \(a+b-1\)

OUTPUT:

  • a Dyck path in the \((a \times b)\)-rectangle

EXAMPLES:

sage: from sage.combinat.tamari_lattices import swap
sage: swap((1,0,1,0,0),1)
(1, 1, 0, 0, 0)
sage: swap((1,1,0,0,1,1,0,0,0),3)
(1, 1, 0, 1, 1, 0, 0, 0, 0)
sage.combinat.tamari_lattices.swap_dexter(p, i)

Perform covering moves in the \((a,b)\)-Dexter posets.

The letter at position \(i\) in \(p\) must be a \(0\), followed by at least one \(1\).

INPUT:

  • p – a Dyck path in the \((a \times b)\)-rectangle

  • i – an integer between \(0\) and \(a+b-1\)

OUTPUT:

  • a list of Dyck paths in the \((a \times b)\)-rectangle

EXAMPLES:

sage: from sage.combinat.tamari_lattices import swap_dexter
sage: swap_dexter((1,0,1,0,0),1)
[(1, 1, 0, 0, 0)]
sage: swap_dexter((1,1,0,0,1,1,0,0,0),3)
[(1, 1, 0, 1, 1, 0, 0, 0, 0), (1, 1, 1, 1, 0, 0, 0, 0, 0)]
sage: swap_dexter((1,1,0,1,0,0,0),2)
[]