Tamari Interval-posets¶
This module implements Tamari interval-posets: combinatorial objects which
represent intervals of the Tamari order. They have been introduced in
[PCh2013] and allow for many combinatorial operations on Tamari intervals.
In particular, they are linked to DyckWords
and BinaryTrees
.
An introduction into Tamari interval-posets 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 [TamBrack1962] [HuangTamari1972] [Sta-EC2]. An interval can be seen as a pair of comparable elements. The number of intervals has been given in [ChapTamari08].
REFERENCES:
[PCh2013] | Grégory Châtel and Viviane Pons. Counting smaller trees in the Tamari order. FPSAC. (2013). Arxiv 1212.0751v1. |
[Pons2013] | Viviane Pons, Combinatoire algébrique liée aux ordres sur les permutations. PhD Thesis. (2013). Arxiv 1310.1805v1. |
[TamBrack1962] | Dov Tamari. The algebra of bracketings and their enumeration. Nieuw Arch. Wisk. (1962). |
[HuangTamari1972] | Samuel Huang and Dov Tamari. Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law. J. Combinatorial Theory Ser. A. (1972). http://www.sciencedirect.com/science/article/pii/0097316572900039 . |
[ChapTamari08] | (1, 2, 3, 4, 5) Frédéric Chapoton. Sur le nombre d’intervalles dans les treillis de Tamari. Sem. Lothar. Combin. (2008). Arxiv math/0602368v1. |
[FPR15] | Wenjie Fang and Louis-François Préville-Ratelle, From generalized Tamari intervals to non-separable planar maps. Arxiv 1511.05937 |
AUTHORS:
- Viviane Pons 2014: initial implementation
- Frederic 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 interval-posets.
An interval-poset 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.
Interval-posets of size \(n\) are in bijection with intervals of the Tamari lattice of binary trees of size \(n\). Specifically, if \(P\) is an interval-poset 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 right-to-left binary search tree (binary_search_tree()
with theleft_to_right
variable set toFalse
) without its labelling.INPUT:
size
– an integer, the size of the interval-posets (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 interval-poset 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 interval-poset. “Minimal” and “maximal” refer to the natural ordering on integers.
The increasing relations of an interval-poset \(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 sub-interval 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 post-order (see :meth:~sage.combinat.abstract_tree.AbstractTree.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 interval-poset \(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 sub-interval 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 pre-order (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 interval-poset condition.
It is also possible to transform a poset directly into an interval-poset:
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
.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 interval-poset
self
.If \(P\) is a Tamari interval-poset of size \(n\), then the complement of \(P\) is defined as the interval-poset \(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 left-right 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 vice-versa.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
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
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 interval-posets, it means that all relations of
self
are relations ofother
.INPUT:
other
– an interval-poset
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
-
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
(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 thatv
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
, i.e., 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 interval-poset formed with only the decreasing relations ofself
.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
-
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
(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
, i.e., the vertices \(a\) ofself
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 interval-poset formed from only the increasing relations ofself
.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 interval-poset
self
.If \(P\) is a Tamari interval-poset 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 interval-poset 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 interval-poset \(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, i-1, 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 \(i-1\) and \(i+1\).
Todo
To study this, it would be more natural to define interval-posets 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)]
TESTS:
Verifying that the two ways of computing insertion are equivalent:
sage: def insert_alternative(T, i): ....: # Just another way to compute the insertion of i into T. ....: from sage.combinat.binary_tree import LabelledBinaryTree ....: B1 = T.lower_binary_tree().canonical_labelling() ....: B2 = T.upper_binary_tree().canonical_labelling() ....: # We should relabel the trees to "make space" for a label i, ....: # but we don't, because it doesn't make a difference: The ....: # binary search insertion will go precisely the same, because ....: # an integer equal to the label of the root gets sent onto ....: # the left branch. ....: C1 = B1.binary_search_insert(i) ....: C2 = B2.binary_search_insert(i) ....: return TamariIntervalPosets.from_binary_trees(C1, C2) sage: def test_equivalence(n): ....: for T in TamariIntervalPosets(n): ....: for i in range(1, n + 2): ....: if not (insert_alternative(T, i) == T.insertion(i)): ....: print(T, i) ....: return False ....: return True sage: test_equivalence(3) True
-
intersection
(other)¶ Return the interval-poset 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 interval-poset 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 interval-poset. sage: ip4 = TamariIntervalPoset(3,[(2,3)]) sage: ip2.intersection(ip4) Traceback (most recent call last): ... ValueError: Intersections are only possible on interval-posets 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.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_exceptional
()¶ Return
True
ifself
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\).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, i.e. if its upper end is the largest element of the lattice. It consists of checking thatself
does not contain any increasing relations.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_initial_interval
()¶ Return if
self
corresponds to an initial interval of the Tamari lattice, i.e. if its lower end is the smallest element of the lattice. It consists of checking thatself
does not contain any decreasing relations.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
True
ifself
is a modern 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\).See also
EXAMPLES:
sage: len([T for T in TamariIntervalPosets(3) if T.is_modern()]) 12
-
is_new
()¶ Return
True
ifself
is a new Tamari interval.Here ‘new’ means that the interval is not contained in any facet of the associahedron.
They have been considered in section 9 of [ChapTamari08].
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
True
ifself
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
True
ifself
is a synchronized Tamari interval.This means that the upper and lower binary trees have the same canopee.
This has been considered in [FPR15]. 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
-
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, 4, 2, 3], [1, 2, 4, 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 left-branch ordered forest (i.e., the result of applying
to_ordered_tree_left_branch()
and cutting off the root) is the final forest ofself
.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 interval-posets, 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 interval-posets, it means that
other
contains the relations ofself
plus some extra increasing relations.INPUT:
other
– an interval-poset
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
.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 132-avoiding 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 312-avoiding 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 interval-poset into new interval-posets.
Every interval-poset has a unique decomposition as a planar tree of new interval-posets, as explained in [ChapTamari08]. 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 interval-posets.
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 []]
TESTS:
sage: ex = TamariIntervalPosets(4).random_element() sage: dec = ex.new_decomposition() sage: len(dec) == ex.number_of_new_components() True sage: all(u.is_new() for u in dec) True
-
number_of_new_components
()¶ Return the number of terms in the decomposition in new interval-posets.
Every interval-poset has a unique decomposition as a planar tree of new interval-posets, as explained in [ChapTamari08]. 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 byself
.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 interval-poset 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
-
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 interval-posets, 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 interval-poset.
EXAMPLES:
sage: TamariIntervalPoset(3,[(2,1),(3,1)]).size() 3
-
sub_poset
(start, end)¶ Return the renormalized sub-poset 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.sub_poset(1,3) The Tamari interval of size 2 induced by relations [(1, 2)] sage: ip.sub_poset(1,4) The Tamari interval of size 3 induced by relations [(1, 2), (3, 2)] sage: ip.sub_poset(1,5) The Tamari interval of size 4 induced by relations [(1, 2), (4, 3), (3, 2)] sage: ip.sub_poset(1,7) == ip True sage: ip.sub_poset(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 interval-poset where \((a,b)\) is the first inversion of \(I\) in lexicographic order, one reduces the inversion number by exactly \(1\).
See also
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 right-branch ordered forest (i.e., the result of applying
to_ordered_tree_right_branch()
and cutting off the root) is the initial forest ofself
.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 interval-posets, it means that
other
contains the relations ofself
plus some extra decreasing relations.INPUT:
other
– an interval-poset
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
.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 interval-posets.
INPUT:
size
– (optional) an integer
OUTPUT:
- the set of all interval-posets (of the given
size
if specified)
EXAMPLES:
sage: TamariIntervalPosets() Interval-posets sage: TamariIntervalPosets(2) Interval-posets 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 interval-poset, 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 interval-poset or a Dyck word.
A final forest is an interval-poset 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 interval-poset
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 [(1, 2), (2, 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 interval-poset corresponding to the interval [
tree1
,tree2
] of the Tamari lattice. Raise an exception iftree1
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 interval-poset corresponding to the interval [
dw1
,dw2
] of the Tamari lattice. Raise an exception if the two Dyck wordsdw1
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_minimal_schnyder_wood
(graph)¶ Return a Tamari interval build from a minimal Schnyder wood.
This is an implementation of Bernardi and Bonichon’s bijection [BerBon].
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 ‘a’, ‘b’ and ‘c’.
One assumes moreover that the embedding around ‘a’ is the list of neighbors of ‘a’ 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 interval poset
EXAMPLES:
A small example:
sage: TIP = TamariIntervalPosets sage: G = DiGraph([(0,'a',0),(0,'b',1),(0,'c',2)], format='list_of_edges') sage: G.set_embedding({'a':[0],'b':[0],'c':[0],0:['a','b','c']}) sage: TIP.from_minimal_schnyder_wood(G) The Tamari interval of size 1 induced by relations []
An example from page 14 of [BerBon]:
sage: c0 = [(0,'a'),(1,0),(2,0),(4,3),(3,'a'),(5,3)] sage: c1 = [(5,'b'),(3,'b'),(4,5),(1,3),(2,3),(0,3)] sage: c2 = [(0,'c'),(1,'c'),(3,'c'),(4,'c'),(5,'c'),(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 = {'a':[3,0],'b':[5,3],'c':[0,1,3,4,5]} sage: data_emb = [[3,2,1,'c','a'],[2,3,'c',0],[3,1,0]] sage: data_emb += [['b',5,4,'c',1,2,0,'a'],[5,'c',3],['b','c',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 [BerBon]:
sage: c0 = [(0,'a'),(1,0),(2,'a'),(3,2),(4,2),(5,'a')] sage: c1 = [(5,'b'),(2,'b'),(4,'b'),(3,4),(1,2),(0,2)] sage: c2 = [(0,'c'),(1,'c'),(3,'c'),(4,'c'),(2,'c'),(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 = {'a':[5,2,0],'b':[4,2,5],'c':[0,1,2,3,4]} sage: data_emb = [[2,1,'c','a'],[2,'c',0],[3,'c',1,0,'a',5,'b',4]] sage: data_emb += [[4,'c',2],['b','c',3,2],['b',2,'a']] 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,'a'),(2,'a'),(1,0)] sage: c1 = [(2,'b'),(1,'b'),(0,2)] sage: c2 = [(0,'c'),(1,'c'),(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 = {'a':[2,0],'b':[1,2],'c':[0,1]} sage: data_emb = [[2,1,'c','a'],['c',0,2,'b'],['b',1,0,'a']] 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)]
REFERENCES:
[BerBon] (1, 2, 3, 4) Olivier Bernardi and Nicolas Bonichon, Intervals in Catalan lattices and realizers of triangulations, JCTA 116 (2009)
-
global_options
(*args, **kwds)¶ Deprecated: Use
options()
instead. See trac ticket #18555 for details.
-
static
initial_forest
(element)¶ Return the inital forest of a binary tree, an interval-poset or a Dyck word.
An initial forest is an interval-poset 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 interval-poset
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 interval-posets through interval containment.
Return whether the interval represented by
el1
is contained in the interval represented byel2
.INPUT:
el1
– an interval-posetel2
– an interval-poset
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 interval-posets. If no parameters are set, then the function returns a copy of the options dictionary.
The
options
to Tamari interval-posets 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: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]) sage: ip.latex_options.color_decreasing 'red' sage: TamariIntervalPosets.options.latex_color_decreasing='green' sage: ip.latex_options.color_decreasing 'green' sage: TamariIntervalPosets.options._reset() sage: ip.latex_options.color_decreasing 'red'
See
GlobalOptions
for more features of these options.
-
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 interval-posets.
-
Element
¶ alias of
TamariIntervalPoset
-
-
class
sage.combinat.interval_posets.
TamariIntervalPosets_size
(size)¶ Bases:
sage.combinat.interval_posets.TamariIntervalPosets
The enumerated set of interval-posets of a given size.
-
cardinality
()¶ The cardinality of
self
. That is, the number of interval-posets of size \(n\).The formula was given in [ChapTamari08]:
\[\frac{2(4n+1)!}{(n+1)!(3n+2)!} = \frac{2}{n(n+1)} \binom{4n+1}{n-1}.\]EXAMPLES:
sage: [TamariIntervalPosets(i).cardinality() for i in range(6)] [1, 1, 3, 13, 68, 399]
-
element_class
()¶ TESTS:
sage: S = TamariIntervalPosets(3) sage: S.element_class <class 'sage.combinat.interval_posets.TamariIntervalPosets_all_with_category.element_class'> sage: S.first().__class__ == TamariIntervalPosets().first().__class__ True
-
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 [BerBon].
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() Interval-posets 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
-