Tamari Intervalposets¶
This module implements Tamari intervalposets: combinatorial objects which
represent intervals of the Tamari order. They have been introduced in
[CP2015] and allow for many combinatorial operations on Tamari intervals.
In particular, they are linked to DyckWords
and BinaryTrees
.
An introduction into Tamari intervalposets is given in Chapter 7
of [Pons2013].
The Tamari lattice can be defined as a lattice structure on either of several classes of Catalan objects, especially binary trees and Dyck paths [Tam1962] [HT1972] [StaEC2]. An interval can be seen as a pair of comparable elements. The number of intervals has been given in [Cha2008].
AUTHORS:
 Viviane Pons 2014: initial implementation
 Frédéric Chapoton 2014: review
 Darij Grinberg 2014: review
 Travis Scrimshaw 2014: review

class
sage.combinat.interval_posets.
TamariIntervalPoset
(parent, size, relations=[], check=True)¶ Bases:
sage.structure.element.Element
The class of Tamari intervalposets.
An intervalposet is a labelled poset of size \(n\), with labels \(1, 2, \ldots, n\), satisfying the following conditions:
 if \(a < c\) (as integers) and \(a\) precedes \(c\) in the poset, then, for all \(b\) such that \(a < b < c\), \(b\) precedes \(c\),
 if \(a < c\) (as integers) and \(c\) precedes \(a\) in the poset, then, for all \(b\) such that \(a < b < c\), \(b\) precedes \(a\).
We use the word “precedes” here to distinguish the poset order and the natural order on numbers. “Precedes” means “is smaller than with respect to the poset structure”; this does not imply a covering relation.
Intervalposets of size \(n\) are in bijection with intervals of the Tamari lattice of binary trees of size \(n\). Specifically, if \(P\) is an intervalposet of size \(n\), then the set of linear extensions of \(P\) (as permutations in \(S_n\)) is an interval in the right weak order (see
permutohedron_lequal()
), and is in fact the preimage of an interval in the Tamari lattice (of binary trees of size \(n\)) under the operation which sends a permutation to its righttoleft binary search tree (binary_search_tree()
with theleft_to_right
variable set toFalse
) without its labelling.INPUT:
size
– an integer, the size of the intervalposets (number of vertices)relations
– a list (or tuple) of pairs(a,b)
(themselves lists or tuples), each representing a relation of the form ‘\(a\) precedes \(b\)‘ in the poset.check
– (default:True
) whether to check the intervalposet condition or not.
Warning
The
relations
input can be a list or tuple, but not an iterator (nor should its entries be iterators).NOTATION:
Here and in the following, the signs \(<\) and \(>\) always refer to the natural ordering on integers, whereas the word “precedes” refers to the order of the intervalposet. “Minimal” and “maximal” refer to the natural ordering on integers.
The increasing relations of an intervalposet \(P\) mean the pairs \((a, b)\) of elements of \(P\) such that \(a < b\) as integers and \(a\) precedes \(b\) in \(P\). The initial forest of \(P\) is the poset obtained by imposing (only) the increasing relations on the ground set of \(P\). It is a subinterval poset of \(P\), and is a forest with its roots on top. This forest is usually given the structure of a planar forest by ordering brother nodes by their labels; it then has the property that if its nodes are traversed in postorder (see
post_order_traversal()
, and traverse the trees of the forest from left to right as well), then the labels encountered are \(1, 2, \ldots, n\) in this order.The decreasing relations of an intervalposet \(P\) mean the pairs \((a, b)\) of elements of \(P\) such that \(b < a\) as integers and \(a\) precedes \(b\) in \(P\). The final forest of \(P\) is the poset obtained by imposing (only) the decreasing relations on the ground set of \(P\). It is a subinterval poset of \(P\), and is a forest with its roots on top. This forest is usually given the structure of a planar forest by ordering brother nodes by their labels; it then has the property that if its nodes are traversed in preorder (see
pre_order_traversal()
, and traverse the trees of the forest from left to right as well), then the labels encountered are \(1, 2, \ldots, n\) in this order.EXAMPLES:
sage: TamariIntervalPoset(0,[]) The Tamari interval of size 0 induced by relations [] sage: TamariIntervalPoset(3,[]) The Tamari interval of size 3 induced by relations [] sage: TamariIntervalPoset(3,[(1,2)]) The Tamari interval of size 3 induced by relations [(1, 2)] sage: TamariIntervalPoset(3,[(1,2),(2,3)]) The Tamari interval of size 3 induced by relations [(1, 2), (2, 3)] sage: TamariIntervalPoset(3,[(1,2),(2,3),(1,3)]) The Tamari interval of size 3 induced by relations [(1, 2), (2, 3)] sage: TamariIntervalPoset(3,[(1,2),(3,2)]) The Tamari interval of size 3 induced by relations [(1, 2), (3, 2)] sage: TamariIntervalPoset(3,[[1,2],[2,3]]) The Tamari interval of size 3 induced by relations [(1, 2), (2, 3)] sage: TamariIntervalPoset(3,[[1,2],[2,3],[1,2],[1,3]]) The Tamari interval of size 3 induced by relations [(1, 2), (2, 3)] sage: TamariIntervalPoset(3,[(3,4)]) Traceback (most recent call last): ... ValueError: the relations do not correspond to the size of the poset sage: TamariIntervalPoset(2,[(2,1),(1,2)]) Traceback (most recent call last): ... ValueError: The graph is not directed acyclic sage: TamariIntervalPoset(3,[(1,3)]) Traceback (most recent call last): ... ValueError: this does not satisfy the Tamari intervalposet condition
It is also possible to transform a poset directly into an intervalposet:
sage: TIP = TamariIntervalPosets() sage: p = Poset(([1,2,3], [(1,2)])) sage: TIP(p) The Tamari interval of size 3 induced by relations [(1, 2)] sage: TIP(Poset({1: []})) The Tamari interval of size 1 induced by relations [] sage: TIP(Poset({})) The Tamari interval of size 0 induced by relations []

binary_trees
()¶ Return an iterator on all the binary trees in the interval represented by
self
.See also
EXAMPLES:
sage: list(TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]).binary_trees()) [[., [[., [., .]], .]], [[., [., [., .]]], .], [., [[[., .], .], .]], [[., [[., .], .]], .]] sage: set(TamariIntervalPoset(4,[]).binary_trees()) == set(BinaryTrees(4)) True

complement
()¶ Return the complement of the intervalposet
self
.If \(P\) is a Tamari intervalposet of size \(n\), then the complement of \(P\) is defined as the intervalposet \(Q\) whose base set is \([n] = \{1, 2, \ldots, n\}\) (just as for \(P\)), but whose order relation has \(a\) precede \(b\) if and only if \(n + 1  a\) precedes \(n + 1  b\) in \(P\).
In terms of the Tamari lattice, the complement is the symmetric of
self
. It is formed from the leftright symmeterized of the binary trees of the interval (switching left and right subtrees, seeleft_right_symmetry()
). In particular, initial intervals are sent to final intervals and viceversa.EXAMPLES:
sage: TamariIntervalPoset(3, [(2, 1), (3, 1)]).complement() The Tamari interval of size 3 induced by relations [(1, 3), (2, 3)] sage: TamariIntervalPoset(0, []).complement() The Tamari interval of size 0 induced by relations [] sage: ip = TamariIntervalPoset(4, [(1, 2), (2, 4), (3, 4)]) sage: ip.complement() == TamariIntervalPoset(4, [(2, 1), (3, 1), (4, 3)]) True sage: ip.lower_binary_tree() == ip.complement().upper_binary_tree().left_right_symmetry() True sage: ip.upper_binary_tree() == ip.complement().lower_binary_tree().left_right_symmetry() True sage: ip.is_initial_interval() True sage: ip.complement().is_final_interval() True

contains_binary_tree
(binary_tree)¶ Return whether the interval represented by
self
contains the binary treebinary_tree
.INPUT:
binary_tree
– a binary tree
See also
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip.contains_binary_tree(BinaryTree([[None,[None,[]]],None])) True sage: ip.contains_binary_tree(BinaryTree([None,[[[],None],None]])) True sage: ip.contains_binary_tree(BinaryTree([[],[[],None]])) False sage: ip.contains_binary_tree(ip.lower_binary_tree()) True sage: ip.contains_binary_tree(ip.upper_binary_tree()) True sage: all(ip.contains_binary_tree(bt) for bt in ip.binary_trees()) True

contains_dyck_word
(dyck_word)¶ Return whether the interval represented by
self
contains the Dyck worddyck_word
.INPUT:
dyck_word
– a Dyck word
See also
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip.contains_dyck_word(DyckWord([1,1,1,0,0,0,1,0])) True sage: ip.contains_dyck_word(DyckWord([1,1,0,1,0,1,0,0])) True sage: ip.contains_dyck_word(DyckWord([1,0,1,1,0,1,0,0])) False sage: ip.contains_dyck_word(ip.lower_dyck_word()) True sage: ip.contains_dyck_word(ip.upper_dyck_word()) True sage: all(ip.contains_dyck_word(bt) for bt in ip.dyck_words()) True

contains_interval
(other)¶ Return whether the interval represented by
other
is contained inself
as an interval of the Tamari lattice.In terms of intervalposets, it means that all relations of
self
are relations ofother
.INPUT:
other
– an intervalposet
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: ip2 = TamariIntervalPoset(4,[(2,3)]) sage: ip2.contains_interval(ip1) True sage: ip3 = TamariIntervalPoset(4,[(2,1)]) sage: ip2.contains_interval(ip3) False sage: ip4 = TamariIntervalPoset(3,[(2,3)]) sage: ip2.contains_interval(ip4) False

decomposition_to_triple
()¶ Decompose an intervalposet into a triple (
left
,right
,r
).For the inverse method, see
TamariIntervalPosets.recomposition_from_triple()
.OUTPUT:
a triple (
left
,right
,r
) whereleft
andright
are intervalposets andr
(an integer) is the parameter of the decomposition.EXAMPLES:
sage: tip = TamariIntervalPoset(8, [(1,2), (2,4), (3,4), (6,7), (3,2), (5,4), (6,4), (8,7)]) sage: tip.decomposition_to_triple() (The Tamari interval of size 3 induced by relations [(1, 2), (3, 2)], The Tamari interval of size 4 induced by relations [(2, 3), (4, 3)], 2) sage: tip == TamariIntervalPosets.recomposition_from_triple(*tip.decomposition_to_triple()) True
REFERENCES:

decreasing_children
(v)¶ Return the children of
v
in the final forest ofself
.INPUT:
v
– an integer representing a vertex ofself
(between 1 andsize
)
OUTPUT:
The list of all children of
v
in the final forest ofself
, in increasing order.EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.decreasing_children(2) [3, 5] sage: ip.decreasing_children(3) [4] sage: ip.decreasing_children(1) []

decreasing_cover_relations
()¶ Return the cover relations of the final forest of
self
.This is the poset formed by keeping only the relations of the form \(a\) precedes \(b\) with \(a > b\).
The final forest of
self
is a forest with its roots being on top. It is also called the decreasing poset ofself
.Warning
This method computes the cover relations of the final forest. This is not identical with the cover relations of
self
which happen to be decreasing!See also
EXAMPLES:
sage: TamariIntervalPoset(4,[(2,1),(3,2),(3,4),(4,2)]).decreasing_cover_relations() [(4, 2), (3, 2), (2, 1)] sage: TamariIntervalPoset(4,[(2,1),(4,3),(2,3)]).decreasing_cover_relations() [(4, 3), (2, 1)] sage: TamariIntervalPoset(3,[(2,1),(3,1),(3,2)]).decreasing_cover_relations() [(3, 2), (2, 1)]

decreasing_parent
(v)¶ Return the vertex parent of
v
in the final forest ofself
.This is the highest (as integer!) vertex \(a < v\) such that
v
precedesa
. If there is no such vertex (that is, \(v\) is a decreasing root), thenNone
is returned.INPUT:
v
– an integer representing a vertex ofself
(between 1 andsize
)
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.decreasing_parent(4) 3 sage: ip.decreasing_parent(3) 2 sage: ip.decreasing_parent(5) 2 sage: ip.decreasing_parent(2) is None True

decreasing_roots
()¶ Return the root vertices of the final forest of
self
.These are the vertices \(b\) such that there is no \(a < b\) with \(b\) preceding \(a\).
OUTPUT:
The list of all roots of the final forest of
self
, in increasing order.EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.decreasing_roots() [1, 2] sage: ip.final_forest().decreasing_roots() [1, 2]

dyck_words
()¶ Return an iterator on all the Dyck words in the interval represented by
self
.EXAMPLES:
sage: list(TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]).dyck_words()) [[1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 0, 1, 0, 0, 1, 0]] sage: set(TamariIntervalPoset(4,[]).dyck_words()) == set(DyckWords(4)) True

final_forest
()¶ Return the final forest of
self
, i.e., the intervalposet formed with only the decreasing relations ofself
.See also
EXAMPLES:
sage: TamariIntervalPoset(4,[(2,1),(3,2),(3,4),(4,2)]).final_forest() The Tamari interval of size 4 induced by relations [(4, 2), (3, 2), (2, 1)] sage: ip = TamariIntervalPoset(3,[(2,1),(3,1)]) sage: ip.final_forest() == ip True

ge
(e1, e2)¶ Return whether
e2
precedes or equalse1
inself
.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip.ge(2,1) True sage: ip.ge(3,1) True sage: ip.ge(3,2) True sage: ip.ge(4,3) False sage: ip.ge(1,1) True

grafting_tree
()¶ Return the grafting tree of the intervalposet.
For the inverse method, see
TamariIntervalPosets.from_grafting_tree()
.EXAMPLES:
sage: tip = TamariIntervalPoset(8, [(1,2), (2,4), (3,4), (6,7), (3,2), (5,4), (6,4), (8,7)]) sage: tip.grafting_tree() 2[1[0[., .], 0[., .]], 0[., 1[0[., .], 0[., .]]]] sage: tip == TamariIntervalPosets.from_grafting_tree(tip.grafting_tree()) True
REFERENCES:

gt
(e1, e2)¶ Return whether
e2
strictly precedese1
inself
.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip.gt(2,1) True sage: ip.gt(3,1) True sage: ip.gt(3,2) True sage: ip.gt(4,3) False sage: ip.gt(1,1) False

increasing_children
(v)¶ Return the children of
v
in the initial forest ofself
.INPUT:
v
– an integer representing a vertex ofself
(between 1 andsize
)
OUTPUT:
The list of all children of
v
in the initial forest ofself
, in decreasing order.EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.increasing_children(2) [1] sage: ip.increasing_children(5) [4, 3] sage: ip.increasing_children(1) []

increasing_cover_relations
()¶ Return the cover relations of the initial forest of
self
.This is the poset formed by keeping only the relations of the form \(a\) precedes \(b\) with \(a < b\).
The initial forest of
self
is a forest with its roots being on top. It is also called the increasing poset ofself
.Warning
This method computes the cover relations of the initial forest. This is not identical with the cover relations of
self
which happen to be increasing!See also
EXAMPLES:
sage: TamariIntervalPoset(4,[(1,2),(3,2),(2,4),(3,4)]).increasing_cover_relations() [(1, 2), (2, 4), (3, 4)] sage: TamariIntervalPoset(3,[(1,2),(1,3),(2,3)]).increasing_cover_relations() [(1, 2), (2, 3)]

increasing_parent
(v)¶ Return the vertex parent of
v
in the initial forest ofself
.This is the lowest (as integer!) vertex \(b > v\) such that \(v\) precedes \(b\). If there is no such vertex (that is, \(v\) is an increasing root), then
None
is returned.INPUT:
v
– an integer representing a vertex ofself
(between 1 andsize
)
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.increasing_parent(1) 2 sage: ip.increasing_parent(3) 5 sage: ip.increasing_parent(4) 5 sage: ip.increasing_parent(5) is None True

increasing_roots
()¶ Return the root vertices of the initial forest of
self
.These are the vertices \(a\) of
self
such that there is no \(b > a\) with \(a\) precedes \(b\).OUTPUT:
The list of all roots of the initial forest of
self
, in decreasing order.EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.increasing_roots() [6, 5, 2] sage: ip.initial_forest().increasing_roots() [6, 5, 2]

initial_forest
()¶ Return the initial forest of
self
, i.e., the intervalposet formed from only the increasing relations ofself
.See also
EXAMPLES:
sage: TamariIntervalPoset(4,[(1,2),(3,2),(2,4),(3,4)]).initial_forest() The Tamari interval of size 4 induced by relations [(1, 2), (2, 4), (3, 4)] sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip.initial_forest() == ip True

insertion
(i)¶ Return the Tamari insertion of an integer \(i\) into the intervalposet
self
.If \(P\) is a Tamari intervalposet of size \(n\) and \(i\) is an integer with \(1 \leq i \leq n+1\), then the Tamari insertion of \(i\) into \(P\) is defined as the Tamari intervalposet of size \(n+1\) which corresponds to the interval \([C_1, C_2]\) on the Tamari lattice, where the binary trees \(C_1\) and \(C_2\) are defined as follows: We write the intervalposet \(P\) as \([B_1, B_2]\) for two binary trees \(B_1\) and \(B_2\). We label the vertices of each of these two trees with the integers \(1, 2, \ldots, i1, i+1, i+2, \ldots, n+1\) in such a way that the trees are binary search trees (this labelling is unique). Then, we insert \(i\) into each of these trees (in the way as explained in
binary_search_insert()
). The shapes of the resulting two trees are denoted \(C_1\) and \(C_2\).An alternative way to construct the insertion of \(i\) into \(P\) is by relabeling each vertex \(u\) of \(P\) satisfying \(u \geq i\) (as integers) as \(u+1\), and then adding a vertex \(i\) which should precede \(i1\) and \(i+1\).
Todo
To study this, it would be more natural to define intervalposets on arbitrary ordered sets rather than just on \(\{1, 2, \ldots, n\}\).
EXAMPLES:
sage: ip = TamariIntervalPoset(4, [(2, 3), (4, 3)]); ip The Tamari interval of size 4 induced by relations [(2, 3), (4, 3)] sage: ip.insertion(1) The Tamari interval of size 5 induced by relations [(1, 2), (3, 4), (5, 4)] sage: ip.insertion(2) The Tamari interval of size 5 induced by relations [(2, 3), (3, 4), (5, 4), (2, 1)] sage: ip.insertion(3) The Tamari interval of size 5 induced by relations [(2, 4), (3, 4), (5, 4), (3, 2)] sage: ip.insertion(4) The Tamari interval of size 5 induced by relations [(2, 3), (4, 5), (5, 3), (4, 3)] sage: ip.insertion(5) The Tamari interval of size 5 induced by relations [(2, 3), (5, 4), (4, 3)] sage: ip = TamariIntervalPoset(0, []) sage: ip.insertion(1) The Tamari interval of size 1 induced by relations [] sage: ip = TamariIntervalPoset(1, []) sage: ip.insertion(1) The Tamari interval of size 2 induced by relations [(1, 2)] sage: ip.insertion(2) The Tamari interval of size 2 induced by relations [(2, 1)]

intersection
(other)¶ Return the intervalposet formed by combining the relations from both
self
andother
. It corresponds to the intersection of the two corresponding intervals of the Tamari lattice.INPUT:
other
– an intervalposet of the same size asself
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip2 = TamariIntervalPoset(4,[(4,3)]) sage: ip1.intersection(ip2) The Tamari interval of size 4 induced by relations [(1, 2), (2, 3), (4, 3)] sage: ip3 = TamariIntervalPoset(4,[(2,1)]) sage: ip1.intersection(ip3) Traceback (most recent call last): ... ValueError: this intersection is empty, it does not correspond to an intervalposet sage: ip4 = TamariIntervalPoset(3,[(2,3)]) sage: ip2.intersection(ip4) Traceback (most recent call last): ... ValueError: intersections are only possible on intervalposets of the same size

interval_cardinality
()¶ Return the cardinality of the interval, i.e., the number of elements (binary trees or Dyck words) in the interval represented by
self
.Not to be confused with
size()
which is the number of vertices.See also
EXAMPLES:
sage: TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]).interval_cardinality() 4 sage: TamariIntervalPoset(4,[]).interval_cardinality() 14 sage: TamariIntervalPoset(4,[(1,2),(2,3),(3,4)]).interval_cardinality() 1

is_connected
()¶ Return whether
self
is a connected Tamari interval.This means that the Hasse diagram is connected.
This condition is invariant under complementation.
See also
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) if T.is_connected()]) 8

is_dexter
()¶ Return whether
self
is a dexter Tamari interval.This is defined by an exclusion pattern in the Hasse diagram. See the code for the exact description.
This condition is not invariant under complementation.
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) if T.is_dexter()]) 12

is_exceptional
()¶ Return whether
self
is an exceptional Tamari interval.This is defined by exclusion of a simple pattern in the Hasse diagram, namely there is no configuration
y < x > z
with \(1 \leq y < x < z \leq n\).This condition is invariant under complementation.
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) ....: if T.is_exceptional()]) 12

is_final_interval
()¶ Return if
self
corresponds to a final interval of the Tamari lattice.This means that its upper end is the largest element of the lattice. It consists of checking that
self
does not contain any increasing relations.See also
EXAMPLES:
sage: ip = TamariIntervalPoset(4, [(4, 3), (3, 1), (2, 1)]) sage: ip.is_final_interval() True sage: ip.upper_dyck_word() [1, 1, 1, 1, 0, 0, 0, 0] sage: ip = TamariIntervalPoset(4, [(4, 3), (3, 1), (2, 1), (2, 3)]) sage: ip.is_final_interval() False sage: ip.upper_dyck_word() [1, 1, 0, 1, 1, 0, 0, 0] sage: all(dw.tamari_interval(DyckWord([1, 1, 1, 0, 0, 0])).is_final_interval() for dw in DyckWords(3)) True

is_indecomposable
()¶ Return whether
self
is an indecomposable Tamari interval.This is the terminology of [Cha2008].
This means that the upper binary tree has an empty left subtree.
This condition is not invariant under complementation.
See also
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) ....: if T.is_indecomposable()]) 8

is_infinitely_modern
()¶ Return whether
self
is an infinitelymodern Tamari interval.This is defined by the exclusion of the configuration \(i \rightarrow i + 1\) and \(j + 1 \rightarrow j\) with \(i < j\).
This condition is invariant under complementation.
See also
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) ....: if T.is_infinitely_modern()]) 12
REFERENCES:

is_initial_interval
()¶ Return if
self
corresponds to an initial interval of the Tamari lattice.This means that its lower end is the smallest element of the lattice. It consists of checking that
self
does not contain any decreasing relations.See also
EXAMPLES:
sage: ip = TamariIntervalPoset(4, [(1, 2), (2, 4), (3, 4)]) sage: ip.is_initial_interval() True sage: ip.lower_dyck_word() [1, 0, 1, 0, 1, 0, 1, 0] sage: ip = TamariIntervalPoset(4, [(1, 2), (2, 4), (3, 4), (3, 2)]) sage: ip.is_initial_interval() False sage: ip.lower_dyck_word() [1, 0, 1, 1, 0, 0, 1, 0] sage: all(DyckWord([1,0,1,0,1,0]).tamari_interval(dw).is_initial_interval() for dw in DyckWords(3)) True

is_linear_extension
(perm)¶ Return whether the permutation
perm
is a linear extension ofself
.INPUT:
perm
– a permutation of the size ofself
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: ip.is_linear_extension([1,4,2,3]) True sage: ip.is_linear_extension(Permutation([1,4,2,3])) True sage: ip.is_linear_extension(Permutation([1,4,3,2])) False

is_modern
()¶ Return whether
self
is a modern Tamari interval.This is defined by exclusion of a simple pattern in the Hasse diagram, namely there is no configuration \(y \rightarrow x \leftarrow z\) with \(1 \leq y < x < z \leq n\).
This condition is invariant under complementation.
See also
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) if T.is_modern()]) 12
REFERENCES:

is_new
()¶ Return whether
self
is a new Tamari interval.Here ‘new’ means that the interval is not contained in any facet of the associahedron. This condition is invariant under complementation.
They have been considered in section 9 of [Cha2008].
See also
EXAMPLES:
sage: TIP4 = TamariIntervalPosets(4) sage: len([u for u in TIP4 if u.is_new()]) 12 sage: TIP3 = TamariIntervalPosets(3) sage: len([u for u in TIP3 if u.is_new()]) 3

is_simple
()¶ Return whether
self
is a simple Tamari interval.Here ‘simple’ means that the interval contains a unique binary tree.
These intervals define the simple modules over the incidence algebras of the Tamari lattices.
See also
EXAMPLES:
sage: TIP4 = TamariIntervalPosets(4) sage: len([u for u in TIP4 if u.is_simple()]) 14 sage: TIP3 = TamariIntervalPosets(3) sage: len([u for u in TIP3 if u.is_simple()]) 5

is_synchronized
()¶ Return whether
self
is a synchronized Tamari interval.This means that the upper and lower binary trees have the same canopee. This condition is invariant under complementation.
This has been considered in [FPR2015]. The numbers of synchronized intervals are given by the sequence OEIS sequence A000139.
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) ....: if T.is_synchronized()]) 6

latex_options
()¶ Return the latex options for use in the
_latex_
function as a dictionary.The default values are set using the options.
tikz_scale
– (default: 1) scale for use with the tikz packageline_width
– (default: 1) value representing the line width (additionally scaled bytikz_scale
)color_decreasing
– (default:'red'
) the color for decreasing relationscolor_increasing
– (default:'blue'
) the color for increasing relationshspace
– (default: 1) the difference between horizontal coordinates of adjacent verticesvspace
– (default: 1) the difference between vertical coordinates of adjacent vertices
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip.latex_options()['color_decreasing'] 'red' sage: ip.latex_options()['hspace'] 1

le
(e1, e2)¶ Return whether
e1
precedes or equalse2
inself
.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip.le(1,2) True sage: ip.le(1,3) True sage: ip.le(2,3) True sage: ip.le(3,4) False sage: ip.le(1,1) True

left_branch_involution
()¶ Return the image of
self
by the leftbranch involution.OUTPUT: an intervalposet
See also
EXAMPLES:
sage: tip = TamariIntervalPoset(8, [(1,2), (2,4), (3,4), (6,7), (3,2), (5,4), (6,4), (8,7)]) sage: t = tip.left_branch_involution(); t The Tamari interval of size 8 induced by relations [(1, 6), (2, 6), (3, 5), (4, 5), (5, 6), (6, 8), (7, 8), (7, 6), (4, 3), (3, 1), (2, 1)] sage: t.left_branch_involution() == tip True
REFERENCES:

linear_extensions
()¶ Return an iterator on the permutations which are linear extensions of
self
.They form an interval of the right weak order (also called the right permutohedron order – see
permutohedron_lequal()
for a definition).EXAMPLES:
sage: ip = TamariIntervalPoset(3,[(1,2),(3,2)]) sage: list(ip.linear_extensions()) [[3, 1, 2], [1, 3, 2]] sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: list(ip.linear_extensions()) [[4, 1, 2, 3], [1, 2, 4, 3], [1, 4, 2, 3]]

lower_binary_tree
()¶ Return the lowest binary tree in the interval of the Tamari lattice represented by
self
.This is a binary tree. It is the shape of the unique binary search tree whose leftbranch ordered forest (i.e., the result of applying
to_ordered_tree_left_branch()
and cutting off the root) is the final forest ofself
.See also
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.lower_binary_tree() [[., .], [[., [., .]], [., .]]] sage: TamariIntervalPosets.final_forest(ip.lower_binary_tree()) == ip.final_forest() True sage: ip == TamariIntervalPosets.from_binary_trees(ip.lower_binary_tree(),ip.upper_binary_tree()) True

lower_contained_intervals
()¶ If
self
represents the interval \([t_1, t_2]\) of the Tamari lattice, return an iterator on all intervals \([t_1,t]\) with \(t \leq t_2\) for the Tamari lattice.In terms of intervalposets, it corresponds to adding all possible relations of the form \(n\) precedes \(m\) with \(n<m\).
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: list(ip.lower_contained_intervals()) [The Tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)], The Tamari interval of size 4 induced by relations [(1, 4), (2, 4), (3, 4), (3, 1), (2, 1)], The Tamari interval of size 4 induced by relations [(2, 3), (3, 4), (3, 1), (2, 1)], The Tamari interval of size 4 induced by relations [(1, 4), (2, 3), (3, 4), (3, 1), (2, 1)]] sage: ip = TamariIntervalPoset(4,[]) sage: len(list(ip.lower_contained_intervals())) 14

lower_contains_interval
(other)¶ Return whether the interval represented by
other
is contained inself
as an interval of the Tamari lattice and if they share the same lower bound.As intervalposets, it means that
other
contains the relations ofself
plus some extra increasing relations.INPUT:
other
– an intervalposet
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: ip2 = TamariIntervalPoset(4,[(4,3)]) sage: ip2.lower_contains_interval(ip1) True sage: ip2.contains_interval(ip1) and ip2.lower_binary_tree() == ip1.lower_binary_tree() True sage: ip3 = TamariIntervalPoset(4,[(4,3),(2,1)]) sage: ip2.contains_interval(ip3) True sage: ip2.lower_binary_tree() == ip3.lower_binary_tree() False sage: ip2.lower_contains_interval(ip3) False

lower_dyck_word
()¶ Return the lowest Dyck word in the interval of the Tamari lattice represented by
self
.See also
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.lower_dyck_word() [1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0] sage: TamariIntervalPosets.final_forest(ip.lower_dyck_word()) == ip.final_forest() True sage: ip == TamariIntervalPosets.from_dyck_words(ip.lower_dyck_word(),ip.upper_dyck_word()) True

lt
(e1, e2)¶ Return whether
e1
strictly precedese2
inself
.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip.lt(1,2) True sage: ip.lt(1,3) True sage: ip.lt(2,3) True sage: ip.lt(3,4) False sage: ip.lt(1,1) False

max_linear_extension
()¶ Return the maximal permutation for the right weak order which is a linear extension of
self
.This is also the maximal permutation in the sylvester class of
self.upper_binary_tree()
and is a 132avoiding permutation.The right weak order is also known as the right permutohedron order. See
permutohedron_lequal()
for its definition.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: ip.max_linear_extension() [4, 1, 2, 3] sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.max_linear_extension() [6, 4, 5, 3, 1, 2] sage: ip = TamariIntervalPoset(0,[]); ip The Tamari interval of size 0 induced by relations [] sage: ip.max_linear_extension() [] sage: ip = TamariIntervalPoset(5, [(1, 4), (2, 4), (3, 4), (5, 4)]); ip The Tamari interval of size 5 induced by relations [(1, 4), (2, 4), (3, 4), (5, 4)] sage: ip.max_linear_extension() [5, 3, 2, 1, 4]

maximal_chain_binary_trees
()¶ Return an iterator on the binary trees forming a longest chain of
self
(regardingself
as an interval of the Tamari lattice).EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: list(ip.maximal_chain_binary_trees()) [[[., [[., .], .]], .], [., [[[., .], .], .]], [., [[., [., .]], .]]] sage: ip = TamariIntervalPoset(4,[]) sage: list(ip.maximal_chain_binary_trees()) [[[[[., .], .], .], .], [[[., [., .]], .], .], [[., [[., .], .]], .], [., [[[., .], .], .]], [., [[., [., .]], .]], [., [., [[., .], .]]], [., [., [., [., .]]]]]

maximal_chain_dyck_words
()¶ Return an iterator on the Dyck words forming a longest chain of
self
(regardingself
as an interval of the Tamari lattice).EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: list(ip.maximal_chain_dyck_words()) [[1, 1, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0, 0]] sage: ip = TamariIntervalPoset(4,[]) sage: list(ip.maximal_chain_dyck_words()) [[1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 0, 0, 1, 0, 1, 0], [1, 1, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 0, 1, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0, 0]]

maximal_chain_tamari_intervals
()¶ Return an iterator on the upper contained intervals of one longest chain of the Tamari interval represented by
self
.If
self
represents the interval \([T_1,T_2]\) of the Tamari lattice, this returns intervals \([T',T_2]\) with \(T'\) following one longest chain between \(T_1\) and \(T_2\).To obtain a longest chain, we use the Tamari inversions of
self
. The elements of the chain are obtained by adding one by one the relations \((b,a)\) from each Tamari inversion \((a,b)\) toself
, where the Tamari inversions are taken in lexicographic order.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: list(ip.maximal_chain_tamari_intervals()) [The Tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)], The Tamari interval of size 4 induced by relations [(2, 4), (3, 4), (4, 1), (3, 1), (2, 1)], The Tamari interval of size 4 induced by relations [(2, 4), (3, 4), (4, 1), (3, 2), (2, 1)]] sage: ip = TamariIntervalPoset(4,[]) sage: list(ip.maximal_chain_tamari_intervals()) [The Tamari interval of size 4 induced by relations [], The Tamari interval of size 4 induced by relations [(2, 1)], The Tamari interval of size 4 induced by relations [(3, 1), (2, 1)], The Tamari interval of size 4 induced by relations [(4, 1), (3, 1), (2, 1)], The Tamari interval of size 4 induced by relations [(4, 1), (3, 2), (2, 1)], The Tamari interval of size 4 induced by relations [(4, 2), (3, 2), (2, 1)], The Tamari interval of size 4 induced by relations [(4, 3), (3, 2), (2, 1)]]

min_linear_extension
()¶ Return the minimal permutation for the right weak order which is a linear extension of
self
.This is also the minimal permutation in the sylvester class of
self.lower_binary_tree()
and is a 312avoiding permutation.The right weak order is also known as the right permutohedron order. See
permutohedron_lequal()
for its definition.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: ip.min_linear_extension() [1, 2, 4, 3] sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]) sage: ip.min_linear_extension() [1, 4, 3, 6, 5, 2] sage: ip = TamariIntervalPoset(0,[]) sage: ip.min_linear_extension() [] sage: ip = TamariIntervalPoset(5, [(1, 4), (2, 4), (3, 4), (5, 4)]); ip The Tamari interval of size 5 induced by relations [(1, 4), (2, 4), (3, 4), (5, 4)] sage: ip.min_linear_extension() [1, 2, 3, 5, 4]

new_decomposition
()¶ Return the decomposition of the intervalposet into new intervalposets.
Every intervalposet has a unique decomposition as a planar tree of new intervalposets, as explained in [Cha2008]. This function computes the terms of this decomposition, but not the planar tree.
For the number of terms, you can use instead the method
number_of_new_components()
.OUTPUT:
a list of new intervalposets.
See also
EXAMPLES:
sage: ex = TamariIntervalPosets(4)[11] sage: ex.number_of_new_components() 3 sage: ex.new_decomposition() [The Tamari interval of size 1 induced by relations [], The Tamari interval of size 2 induced by relations [], The Tamari interval of size 1 induced by relations []]

number_of_new_components
()¶ Return the number of terms in the decomposition in new intervalposets.
Every intervalposet has a unique decomposition as a planar tree of new intervalposets, as explained in [Cha2008]. This function just computes the number of terms, not the planar tree nor the terms themselves.
See also
EXAMPLES:
sage: TIP4 = TamariIntervalPosets(4) sage: nb = [u.number_of_new_components() for u in TIP4] sage: [nb.count(i) for i in range(1, 5)] [12, 21, 21, 14]

number_of_tamari_inversions
()¶ Return the number of Tamari inversions of
self
.This is also the length the longest chain of the Tamari interval represented by
self
.EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip.number_of_tamari_inversions() 2 sage: ip = TamariIntervalPoset(4,[]) sage: ip.number_of_tamari_inversions() 6 sage: ip = TamariIntervalPoset(3,[]) sage: ip.number_of_tamari_inversions() 3

plot
(**kwds)¶ Return a picture.
The picture represents the Hasse diagram, where the covers are colored in blue if they are increasing and in red if they are decreasing.
This uses the same coordinates as the latex view.
EXAMPLES:
sage: ti = TamariIntervalPosets(4)[2] sage: ti.plot() Graphics object consisting of 6 graphics primitives

poset
()¶ Return
self
as a labelled poset.An intervalposet is indeed constructed from a labelled poset which is stored internally. This method allows to access the poset and all the associated methods.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(3,2),(2,4),(3,4)]) sage: pos = ip.poset(); pos Finite poset containing 4 elements sage: pos.maximal_chains() [[3, 2, 4], [1, 2, 4]] sage: pos.maximal_elements() [4] sage: pos.is_lattice() False

rise_contact_involution
()¶ Return the image of
self
by the risecontact involution.OUTPUT: an intervalposet
This is defined by conjugating the complement involution by the leftbranch involution.
See also
EXAMPLES:
sage: tip = TamariIntervalPoset(8, [(1,2), (2,4), (3,4), (6,7), (3,2), (5,4), (6,4), (8,7)]) sage: t = tip.rise_contact_involution(); t The Tamari interval of size 8 induced by relations [(2, 8), (3, 8), (4, 5), (5, 7), (6, 7), (7, 8), (8, 1), (7, 2), (6, 2), (5, 3), (4, 3), (3, 2), (2, 1)] sage: t.rise_contact_involution() == tip True sage: tip.lower_dyck_word().number_of_touch_points() == t.upper_dyck_word().number_of_initial_rises() True sage: tip.number_of_tamari_inversions() == t.number_of_tamari_inversions() True
REFERENCES:

set_latex_options
(D)¶ Set the latex options for use in the
_latex_
function.The default values are set in the
__init__
function.tikz_scale
– (default: 1) scale for use with the tikz packageline_width
– (default: 1 *tikz_scale
) value representing the line widthcolor_decreasing
– (default: red) the color for decreasing relationscolor_increasing
– (default: blue) the color for increasing relationshspace
– (default: 1) the difference between horizontal coordinates of adjacent verticesvspace
– (default: 1) the difference between vertical coordinates of adjacent vertices
INPUT:
D
– a dictionary with a list of latex parameters to change
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip.latex_options()["color_decreasing"] 'red' sage: ip.set_latex_options({"color_decreasing":'green'}) sage: ip.latex_options()["color_decreasing"] 'green' sage: ip.set_latex_options({"color_increasing":'black'}) sage: ip.latex_options()["color_increasing"] 'black'
To change the default options for all intervalposets, use the parent’s latex options:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip2 = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip.latex_options()["color_decreasing"] 'red' sage: ip2.latex_options()["color_decreasing"] 'red' sage: TamariIntervalPosets.options(latex_color_decreasing='green') sage: ip.latex_options()["color_decreasing"] 'green' sage: ip2.latex_options()["color_decreasing"] 'green'
Next we set a local latex option and show the global option does not override it:
sage: ip.set_latex_options({"color_decreasing": 'black'}) sage: ip.latex_options()["color_decreasing"] 'black' sage: TamariIntervalPosets.options(latex_color_decreasing='blue') sage: ip.latex_options()["color_decreasing"] 'black' sage: ip2.latex_options()["color_decreasing"] 'blue' sage: TamariIntervalPosets.options._reset()

size
()¶ Return the size (number of vertices) of the intervalposet.
EXAMPLES:
sage: TamariIntervalPoset(3,[(2,1),(3,1)]).size() 3

sub_poset
(start, end)¶ Return the renormalized subposet of
self
consisting solely of integers fromstart
(inclusive) toend
(not inclusive).“Renormalized” means that these integers are relabelled \(1,2,\ldots,k\) in the obvious way (i.e., by subtracting
start  1
).INPUT:
start
– an integer, the starting vertex (inclusive)end
– an integer, the ending vertex (not inclusive)
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.subposet(1,3) The Tamari interval of size 2 induced by relations [(1, 2)] sage: ip.subposet(1,4) The Tamari interval of size 3 induced by relations [(1, 2), (3, 2)] sage: ip.subposet(1,5) The Tamari interval of size 4 induced by relations [(1, 2), (4, 3), (3, 2)] sage: ip.subposet(1,7) == ip True sage: ip.subposet(1,1) The Tamari interval of size 0 induced by relations []

subposet
(start, end)¶ Return the renormalized subposet of
self
consisting solely of integers fromstart
(inclusive) toend
(not inclusive).“Renormalized” means that these integers are relabelled \(1,2,\ldots,k\) in the obvious way (i.e., by subtracting
start  1
).INPUT:
start
– an integer, the starting vertex (inclusive)end
– an integer, the ending vertex (not inclusive)
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.subposet(1,3) The Tamari interval of size 2 induced by relations [(1, 2)] sage: ip.subposet(1,4) The Tamari interval of size 3 induced by relations [(1, 2), (3, 2)] sage: ip.subposet(1,5) The Tamari interval of size 4 induced by relations [(1, 2), (4, 3), (3, 2)] sage: ip.subposet(1,7) == ip True sage: ip.subposet(1,1) The Tamari interval of size 0 induced by relations []

tamari_inversions
()¶ Return the Tamari inversions of
self
.A Tamari inversion is a pair of vertices \((a,b)\) with \(a < b\) such that:
 the decreasing parent of \(b\) is strictly smaller than \(a\) (or does not exist), and
 the increasing parent of \(a\) is strictly bigger than \(b\) (or does not exist).
“Smaller” and “bigger” refer to the numerical values of the elements, not to the poset order.
This method returns the list of all Tamari inversions in lexicographic order.
The number of Tamari inversions is the length of the longest chain of the Tamari interval represented by
self
.Indeed, when an interval consists of just one binary tree, it has no inversion. One can also prove that if a Tamari interval \(I' = [T_1', T_2']\) is a proper subset of a Tamari interval \(I = [T_1, T_2]\), then the inversion number of \(I'\) is strictly lower than the inversion number of \(I\). And finally, by adding the relation \((b,a)\) to the intervalposet where \((a,b)\) is the first inversion of \(I\) in lexicographic order, one reduces the inversion number by exactly \(1\).
EXAMPLES:
sage: ip = TamariIntervalPoset(3,[]) sage: ip.tamari_inversions() [(1, 2), (1, 3), (2, 3)] sage: ip = TamariIntervalPoset(3,[(2,1)]) sage: ip.tamari_inversions() [(1, 3), (2, 3)] sage: ip = TamariIntervalPoset(3,[(1,2)]) sage: ip.tamari_inversions() [(2, 3)] sage: ip = TamariIntervalPoset(3,[(1,2),(3,2)]) sage: ip.tamari_inversions() [] sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip.tamari_inversions() [(1, 4), (2, 3)] sage: ip = TamariIntervalPoset(4,[]) sage: ip.tamari_inversions() [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] sage: all(len(TamariIntervalPosets.from_binary_trees(bt,bt).tamari_inversions())==0 for bt in BinaryTrees(3)) True sage: all(len(TamariIntervalPosets.from_binary_trees(bt,bt).tamari_inversions())==0 for bt in BinaryTrees(4)) True

tamari_inversions_iter
()¶ Iterate over the Tamari inversions of
self
, in lexicographic order.See
tamari_inversions()
for the definition of the terms involved.EXAMPLES:
sage: T = TamariIntervalPoset(5, [[1,2],[3,4],[3,2],[5,2],[4,2]]) sage: list(T.tamari_inversions_iter()) [(4, 5)] sage: T = TamariIntervalPoset(8, [(2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (8, 7), (6, 4), (5, 4), (4, 3), (3, 2)]) sage: list(T.tamari_inversions_iter()) [(1, 2), (1, 7), (5, 6)] sage: T = TamariIntervalPoset(1, []) sage: list(T.tamari_inversions_iter()) [] sage: T = TamariIntervalPoset(0, []) sage: list(T.tamari_inversions_iter()) []

upper_binary_tree
()¶ Return the highest binary tree in the interval of the Tamari lattice represented by
self
.This is a binary tree. It is the shape of the unique binary search tree whose rightbranch ordered forest (i.e., the result of applying
to_ordered_tree_right_branch()
and cutting off the root) is the initial forest ofself
.See also
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.upper_binary_tree() [[., .], [., [[., .], [., .]]]] sage: TamariIntervalPosets.initial_forest(ip.upper_binary_tree()) == ip.initial_forest() True sage: ip == TamariIntervalPosets.from_binary_trees(ip.lower_binary_tree(),ip.upper_binary_tree()) True

upper_contains_interval
(other)¶ Return whether the interval represented by
other
is contained inself
as an interval of the Tamari lattice and if they share the same upper bound.As intervalposets, it means that
other
contains the relations ofself
plus some extra decreasing relations.INPUT:
other
– an intervalposet
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: ip2 = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip2.upper_contains_interval(ip1) True sage: ip2.contains_interval(ip1) and ip2.upper_binary_tree() == ip1.upper_binary_tree() True sage: ip3 = TamariIntervalPoset(4,[(1,2),(2,3),(3,4)]) sage: ip2.upper_contains_interval(ip3) False sage: ip2.contains_interval(ip3) True sage: ip2.upper_binary_tree() == ip3.upper_binary_tree() False

upper_dyck_word
()¶ Return the highest Dyck word in the interval of the Tamari lattice represented by
self
.See also
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip The Tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: ip.upper_dyck_word() [1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0] sage: TamariIntervalPosets.initial_forest(ip.upper_dyck_word()) == ip.initial_forest() True sage: ip == TamariIntervalPosets.from_dyck_words(ip.lower_dyck_word(),ip.upper_dyck_word()) True

class
sage.combinat.interval_posets.
TamariIntervalPosets
¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
Factory for intervalposets.
INPUT:
size
– (optional) an integer
OUTPUT:
 the set of all intervalposets (of the given
size
if specified)
EXAMPLES:
sage: TamariIntervalPosets() Intervalposets sage: TamariIntervalPosets(2) Intervalposets of size 2
Note
This is a factory class whose constructor returns instances of subclasses.

static
check_poset
(poset)¶ Check if the given poset
poset
is a intervalposet, that is, if it satisfies the following properties: Its labels are exactly \(1, \ldots, n\) where \(n\) is its size.
 If \(a < c\) (as numbers) and \(a\) precedes \(c\), then \(b\) precedes \(c\) for all \(b\) such that \(a < b < c\).
 If \(a < c\) (as numbers) and \(c\) precedes \(a\), then \(b\) precedes \(a\) for all \(b\) such that \(a < b < c\).
INPUT:
poset
– a finite labeled poset
EXAMPLES:
sage: p = Poset(([1,2,3],[(1,2),(3,2)])) sage: TamariIntervalPosets.check_poset(p) True sage: p = Poset(([2,3],[(3,2)])) sage: TamariIntervalPosets.check_poset(p) False sage: p = Poset(([1,2,3],[(3,1)])) sage: TamariIntervalPosets.check_poset(p) False sage: p = Poset(([1,2,3],[(1,3)])) sage: TamariIntervalPosets.check_poset(p) False

static
final_forest
(element)¶ Return the final forest of a binary tree, an intervalposet or a Dyck word.
A final forest is an intervalposet corresponding to a final interval of the Tamari lattice, i.e., containing only decreasing relations.
It can be constructed from a binary tree by its binary search tree labeling with the rule: \(b\) precedes \(a\) in the final forest iff \(b\) is in the right subtree of \(a\) in the binary search tree.
INPUT:
element
– a binary tree, a Dyck word or an intervalposet
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: TamariIntervalPosets.final_forest(ip) The Tamari interval of size 4 induced by relations [(4, 3)]
From binary trees:
sage: bt = BinaryTree(); bt . sage: TamariIntervalPosets.final_forest(bt) The Tamari interval of size 0 induced by relations [] sage: bt = BinaryTree([]); bt [., .] sage: TamariIntervalPosets.final_forest(bt) The Tamari interval of size 1 induced by relations [] sage: bt = BinaryTree([[],None]); bt [[., .], .] sage: TamariIntervalPosets.final_forest(bt) The Tamari interval of size 2 induced by relations [] sage: bt = BinaryTree([None,[]]); bt [., [., .]] sage: TamariIntervalPosets.final_forest(bt) The Tamari interval of size 2 induced by relations [(2, 1)] sage: bt = BinaryTree([[],[]]); bt [[., .], [., .]] sage: TamariIntervalPosets.final_forest(bt) The Tamari interval of size 3 induced by relations [(3, 2)] sage: bt = BinaryTree([[None,[[],None]],[]]); bt [[., [[., .], .]], [., .]] sage: TamariIntervalPosets.final_forest(bt) The Tamari interval of size 5 induced by relations [(5, 4), (3, 1), (2, 1)]
From Dyck words:
sage: dw = DyckWord([1,0]) sage: TamariIntervalPosets.final_forest(dw) The Tamari interval of size 1 induced by relations [] sage: dw = DyckWord([1,1,0,1,0,0,1,1,0,0]) sage: TamariIntervalPosets.final_forest(dw) The Tamari interval of size 5 induced by relations [(5, 4), (3, 1), (2, 1)]

static
from_binary_trees
(tree1, tree2)¶ Return the intervalposet corresponding to the interval [
tree1
,tree2
] of the Tamari lattice.Raise an exception if
tree1
is not \(\leq\)tree2
in the Tamari lattice.INPUT:
tree1
– a binary treetree2
– a binary tree greater or equal thantree1
for the Tamari lattice
EXAMPLES:
sage: tree1 = BinaryTree([[],None]) sage: tree2 = BinaryTree([None,[]]) sage: TamariIntervalPosets.from_binary_trees(tree1,tree2) The Tamari interval of size 2 induced by relations [] sage: TamariIntervalPosets.from_binary_trees(tree1,tree1) The Tamari interval of size 2 induced by relations [(1, 2)] sage: TamariIntervalPosets.from_binary_trees(tree2,tree2) The Tamari interval of size 2 induced by relations [(2, 1)] sage: tree1 = BinaryTree([[],[[None,[]],[]]]) sage: tree2 = BinaryTree([None,[None,[None,[[],[]]]]]) sage: TamariIntervalPosets.from_binary_trees(tree1,tree2) The Tamari interval of size 6 induced by relations [(4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: tree3 = BinaryTree([None,[None,[[],[None,[]]]]]) sage: TamariIntervalPosets.from_binary_trees(tree1,tree3) Traceback (most recent call last): ... ValueError: the two binary trees are not comparable on the Tamari lattice sage: TamariIntervalPosets.from_binary_trees(tree1,BinaryTree()) Traceback (most recent call last): ... ValueError: the two binary trees are not comparable on the Tamari lattice

static
from_dyck_words
(dw1, dw2)¶ Return the intervalposet corresponding to the interval [
dw1
,dw2
] of the Tamari lattice.Raise an exception if the two Dyck words
dw1
anddw2
do not satisfydw1
\(\leq\)dw2
in the Tamari lattice.INPUT:
dw1
– a Dyck worddw2
– a Dyck word greater or equal thandw1
for the Tamari lattice
EXAMPLES:
sage: dw1 = DyckWord([1,0,1,0]) sage: dw2 = DyckWord([1,1,0,0]) sage: TamariIntervalPosets.from_dyck_words(dw1,dw2) The Tamari interval of size 2 induced by relations [] sage: TamariIntervalPosets.from_dyck_words(dw1,dw1) The Tamari interval of size 2 induced by relations [(1, 2)] sage: TamariIntervalPosets.from_dyck_words(dw2,dw2) The Tamari interval of size 2 induced by relations [(2, 1)] sage: dw1 = DyckWord([1,0,1,1,1,0,0,1,1,0,0,0]) sage: dw2 = DyckWord([1,1,1,1,0,1,1,0,0,0,0,0]) sage: TamariIntervalPosets.from_dyck_words(dw1,dw2) The Tamari interval of size 6 induced by relations [(4, 5), (6, 5), (5, 2), (4, 3), (3, 2)] sage: dw3 = DyckWord([1,1,1,0,1,1,1,0,0,0,0,0]) sage: TamariIntervalPosets.from_dyck_words(dw1,dw3) Traceback (most recent call last): ... ValueError: the two Dyck words are not comparable on the Tamari lattice sage: TamariIntervalPosets.from_dyck_words(dw1,DyckWord([1,0])) Traceback (most recent call last): ... ValueError: the two Dyck words are not comparable on the Tamari lattice

static
from_grafting_tree
(tree)¶ Return an intervalposet from a grafting tree.
For the inverse method, see
TamariIntervalPoset.grafting_tree()
.EXAMPLES:
sage: tip = TamariIntervalPoset(8, [(1,2), (2,4), (3,4), (6,7), (3,2), (5,4), (6,4), (8,7)]) sage: t = tip.grafting_tree() sage: TamariIntervalPosets.from_grafting_tree(t) == tip True
REFERENCES:

static
from_minimal_schnyder_wood
(graph)¶ Return a Tamari interval built from a minimal Schnyder wood.
This is an implementation of Bernardi and Bonichon’s bijection [BeBo2009].
INPUT:
a minimal Schnyder wood, given as a graph with colored and oriented edges, without the three exterior unoriented edges
The three boundary vertices must be 1, 2 and 3.
One assumes moreover that the embedding around 1 is the list of neighbors of 1 and not just a cyclic permutation of that.
Beware that the embedding convention used here is the opposite of the one used by the plot method.
OUTPUT:
a Tamari intervalposet
EXAMPLES:
A small example:
sage: TIP = TamariIntervalPosets sage: G = DiGraph([(0,1,0),(0,2,1),(0,3,2)], format='list_of_edges') sage: G.set_embedding({1:[0],2:[0],3:[0],0:[1,2,3]}) sage: TIP.from_minimal_schnyder_wood(G) The Tamari interval of size 1 induced by relations []
An example from page 14 of [BeBo2009]:
sage: c0 = [(0,1),(1,0),(2,0),(4,3),(3,1),(5,3)] sage: c1 = [(5,2),(3,2),(4,5),(1,3),(2,3),(0,3)] sage: c2 = [(0,3),(1,3),(3,3),(4,3),(5,3),(2,1)] sage: ed = [(u,v,0) for u,v in c0] sage: ed += [(u,v,1) for u,v in c1] sage: ed += [(u,v,2) for u,v in c2] sage: G = DiGraph(ed, format='list_of_edges') sage: embed = {1:[3,0],2:[5,3],3:[0,1,3,4,5]} sage: data_emb = [[3,2,1,3,1],[2,3,3,0],[3,1,0]] sage: data_emb += [[2,5,4,3,1,2,0,1],[5,3,3],[2,3,4,3]] sage: for k in range(6): ....: embed[k] = data_emb[k] sage: G.set_embedding(embed) sage: TIP.from_minimal_schnyder_wood(G) The Tamari interval of size 6 induced by relations [(1, 4), (2, 4), (3, 4), (5, 6), (6, 4), (5, 4), (3, 1), (2, 1)]
An example from page 18 of [BeBo2009]:
sage: c0 = [(0,1),(1,0),(2,1),(3,2),(4,2),(5,1)] sage: c1 = [(5,2),(2,2),(4,2),(3,4),(1,2),(0,2)] sage: c2 = [(0,3),(1,3),(3,3),(4,3),(2,3),(5,2)] sage: ed = [(u,v,0) for u,v in c0] sage: ed += [(u,v,1) for u,v in c1] sage: ed += [(u,v,2) for u,v in c2] sage: G = DiGraph(ed, format='list_of_edges') sage: embed = {1:[5,2,0],2:[4,2,5],3:[0,1,2,3,4]} sage: data_emb = [[2,1,3,1],[2,3,0],[3,3,1,0,1,5,2,4]] sage: data_emb += [[4,3,2],[2,3,3,2],[2,2,1]] sage: for k in range(6): ....: embed[k] = data_emb[k] sage: G.set_embedding(embed) sage: TIP.from_minimal_schnyder_wood(G) The Tamari interval of size 6 induced by relations [(1, 3), (2, 3), (4, 5), (5, 3), (4, 3), (2, 1)]
Another small example:
sage: c0 = [(0,1),(2,1),(1,0)] sage: c1 = [(2,2),(1,2),(0,2)] sage: c2 = [(0,3),(1,3),(2,1)] sage: ed = [(u,v,0) for u,v in c0] sage: ed += [(u,v,1) for u,v in c1] sage: ed += [(u,v,2) for u,v in c2] sage: G = DiGraph(ed, format='list_of_edges') sage: embed = {1:[2,0],2:[1,2],3:[0,1]} sage: data_emb = [[2,1,3,1],[3,0,2,2],[2,1,0,1]] sage: for k in range(3): ....: embed[k] = data_emb[k] sage: G.set_embedding(embed) sage: TIP.from_minimal_schnyder_wood(G) The Tamari interval of size 3 induced by relations [(2, 3), (2, 1)]

static
initial_forest
(element)¶ Return the initial forest of a binary tree, an intervalposet or a Dyck word.
An initial forest is an intervalposet corresponding to an initial interval of the Tamari lattice, i.e., containing only increasing relations.
It can be constructed from a binary tree by its binary search tree labeling with the rule: \(a\) precedes \(b\) in the initial forest iff \(a\) is in the left subtree of \(b\) in the binary search tree.
INPUT:
element
– a binary tree, a Dyck word or an intervalposet
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: TamariIntervalPosets.initial_forest(ip) The Tamari interval of size 4 induced by relations [(1, 2), (2, 3)]
with binary trees:
sage: bt = BinaryTree(); bt . sage: TamariIntervalPosets.initial_forest(bt) The Tamari interval of size 0 induced by relations [] sage: bt = BinaryTree([]); bt [., .] sage: TamariIntervalPosets.initial_forest(bt) The Tamari interval of size 1 induced by relations [] sage: bt = BinaryTree([[],None]); bt [[., .], .] sage: TamariIntervalPosets.initial_forest(bt) The Tamari interval of size 2 induced by relations [(1, 2)] sage: bt = BinaryTree([None,[]]); bt [., [., .]] sage: TamariIntervalPosets.initial_forest(bt) The Tamari interval of size 2 induced by relations [] sage: bt = BinaryTree([[],[]]); bt [[., .], [., .]] sage: TamariIntervalPosets.initial_forest(bt) The Tamari interval of size 3 induced by relations [(1, 2)] sage: bt = BinaryTree([[None,[[],None]],[]]); bt [[., [[., .], .]], [., .]] sage: TamariIntervalPosets.initial_forest(bt) The Tamari interval of size 5 induced by relations [(1, 4), (2, 3), (3, 4)]
from Dyck words:
sage: dw = DyckWord([1,0]) sage: TamariIntervalPosets.initial_forest(dw) The Tamari interval of size 1 induced by relations [] sage: dw = DyckWord([1,1,0,1,0,0,1,1,0,0]) sage: TamariIntervalPosets.initial_forest(dw) The Tamari interval of size 5 induced by relations [(1, 4), (2, 3), (3, 4)]

le
(el1, el2)¶ Poset stucture on the set of intervalposets through interval containment.
Return whether the interval represented by
el1
is contained in the interval represented byel2
.INPUT:
el1
– an intervalposetel2
– an intervalposet
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]) sage: ip2 = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: TamariIntervalPosets().le(ip1,ip2) True sage: TamariIntervalPosets().le(ip2,ip1) False

options
(*get_value, **set_value)¶ Set and display the options for Tamari intervalposets.
If no parameters are set, then the function returns a copy of the options dictionary.
The
options
to Tamari intervalposets can be accessed as the methodTamariIntervalPosets.options()
ofTamariIntervalPosets
and related parent classes.OPTIONS:
latex_color_decreasing
– (default:red
) the default color of decreasing relations when latexedlatex_color_increasing
– (default:blue
) the default color of increasing relations when latexedlatex_hspace
– (default:1
) the default difference between horizontal coordinates of vertices when latexedlatex_line_width_scalar
– (default:0.5
) the default value for the line width as amultiple of the tikz scale when latexedlatex_tikz_scale
– (default:1
) the default value for the tikz scale when latexedlatex_vspace
– (default:1
) the default difference between vertical coordinates of vertices when latexed
EXAMPLES:
sage: TIP = TamariIntervalPosets sage: TIP.options.latex_color_decreasing red sage: TIP.options.latex_color_decreasing='green' sage: TIP.options.latex_color_decreasing green sage: TIP.options._reset() sage: TIP.options.latex_color_decreasing red
See
GlobalOptions
for more features of these options.

static
recomposition_from_triple
(left, right, r)¶ Recompose an intervalposet from a triple (
left
,right
,r
).For the inverse method, see
TamariIntervalPoset.decomposition_to_triple()
.INPUT:
left
– an intervalposetright
– an intervalposetr
– the parameter of the decomposition, an integer
OUTPUT: an intervalposet
EXAMPLES:
sage: T1 = TamariIntervalPoset(3, [(1, 2), (3, 2)]) sage: T2 = TamariIntervalPoset(4, [(2, 3), (4, 3)]) sage: TamariIntervalPosets.recomposition_from_triple(T1, T2, 2) The Tamari interval of size 8 induced by relations [(1, 2), (2, 4), (3, 4), (6, 7), (8, 7), (6, 4), (5, 4), (3, 2)]
REFERENCES:

class
sage.combinat.interval_posets.
TamariIntervalPosets_all
¶ Bases:
sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets
,sage.combinat.interval_posets.TamariIntervalPosets
The enumerated set of all Tamari intervalposets.

Element
¶ alias of
TamariIntervalPoset

one
()¶ Return the unit of the monoid.
This is the empty interval poset, of size 0.
EXAMPLES:
sage: TamariIntervalPosets().one() The Tamari interval of size 0 induced by relations []


class
sage.combinat.interval_posets.
TamariIntervalPosets_size
(size)¶ Bases:
sage.combinat.interval_posets.TamariIntervalPosets
The enumerated set of intervalposets of a given size.

cardinality
()¶ The cardinality of
self
. That is, the number of intervalposets of size \(n\).The formula was given in [Cha2008]:
\[\frac{2(4n+1)!}{(n+1)!(3n+2)!} = \frac{2}{n(n+1)} \binom{4n+1}{n1}.\]EXAMPLES:
sage: [TamariIntervalPosets(i).cardinality() for i in range(6)] [1, 1, 3, 13, 68, 399]

element_class
()¶

random_element
()¶ Return a random Tamari interval of fixed size.
This is obtained by first creating a random rooted planar triangulation, then computing its unique minimal Schnyder wood, then applying a bijection of Bernardi and Bonichon [BeBo2009].
Because the random rooted planar triangulation is chosen uniformly at random, the Tamari interval is also chosen according to the uniform distribution.
EXAMPLES:
sage: T = TamariIntervalPosets(4).random_element() sage: T.parent() Intervalposets sage: u = T.lower_dyck_word(); u # random [1, 1, 0, 1, 0, 0, 1, 0] sage: v = T.lower_dyck_word(); v # random [1, 1, 0, 1, 0, 0, 1, 0] sage: len(u) 8
