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:

• [Cha18]

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:

• [BMFPR]

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)
[]