Tamari Interval-posets#
This module implements Tamari interval-posets: 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 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 [Tam1962] [HT1972] [Sta-EC2]. 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
- sage.combinat.interval_posets.TIP#
alias of
TamariIntervalPoset
- class sage.combinat.interval_posets.TamariIntervalPoset(parent, size, relations=None, check=True)#
Bases:
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
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
.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 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 symmetrized 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
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: # needs sage.combinat 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
- cubical_coordinates()#
Return the cubical coordinates of
self
.This provides a fast and natural way to order the set of interval-posets of a given size.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)]) sage: ip.cubical_coordinates() (-1, -2, 0)
REFERENCES:
- decomposition_to_triple()#
Decompose an interval-poset into a triple (
left
,right
,r
).For the inverse method, see
TamariIntervalPosets.recomposition_from_triple()
.OUTPUT:
a triple (
left
,right
,r
) whereleft
andright
are interval-posets 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()) # needs sage.combinat [[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)) # needs sage.combinat True
- factor()#
Return the unique decomposition as a list of connected components.
EXAMPLES:
sage: factor(TamariIntervalPoset(2,[])) # indirect doctest [The Tamari interval of size 1 induced by relations [], The Tamari interval of size 1 induced by relations []]
See also
- final_forest()#
Return the final forest of
self
, i.e., the interval-poset 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 interval-poset.
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 interval-poset 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 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)]
- 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.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() # needs sage.combinat [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() # needs sage.combinat [1, 1, 0, 1, 1, 0, 0, 0] sage: all(dw.tamari_interval(DyckWord([1, 1, 1, 0, 0, 0])) # needs sage.combinat ....: .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 infinitely-modern 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() # needs sage.combinat [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() # needs sage.combinat [1, 0, 1, 1, 0, 0, 1, 0] sage: all(DyckWord([1,0,1,0,1,0]).tamari_interval(dw) # needs sage.combinat ....: .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 left-branch involution.OUTPUT: an interval-poset
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()) # needs sage.modules sage.rings.finite_rings [[3, 1, 2], [1, 3, 2]] sage: ip = TamariIntervalPoset(4, [(1,2),(2,3),(4,3)]) sage: list(ip.linear_extensions()) # needs sage.modules sage.rings.finite_rings [[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 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
.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 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
.See also
EXAMPLES:
sage: # needs sage.combinat 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: ldw_ff = TamariIntervalPosets.final_forest(ip.lower_dyck_word()) sage: ldw_ff == 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()) # needs sage.combinat [[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()) # needs sage.combinat [[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 [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 interval-posets.
See also
EXAMPLES:
sage: ex = TamariIntervalPosets(4)[11] sage: ex.number_of_new_components() 3 sage: ex.new_decomposition() # needs sage.combinat [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 interval-posets.
Every interval-poset has a unique decomposition as a planar tree of new interval-posets, 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() # needs sage.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
- rise_contact_involution()#
Return the image of
self
by the rise-contact involution.OUTPUT: an interval-poset
This is defined by conjugating the complement involution by the left-branch 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() # needs sage.combinat ....: == 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 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 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 interval-poset 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(not TamariIntervalPosets.from_binary_trees(bt,bt) # needs sage.combinat ....: .tamari_inversions() ....: for bt in BinaryTrees(3)) True sage: all(not TamariIntervalPosets.from_binary_trees(bt,bt) # needs sage.combinat ....: .tamari_inversions() ....: 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
.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 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
.See also
EXAMPLES:
sage: # needs sage.combinat 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: udw_if = TamariIntervalPosets.initial_forest(ip.upper_dyck_word()) sage: udw_if == 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:
UniqueRepresentation
,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 [(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: # needs sage.combinat 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 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 interval-poset 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: # needs sage.combinat 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: # needs sage.combinat 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 interval-poset 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 interval-poset
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) # needs sage.combinat 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) # needs sage.combinat 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) # needs sage.combinat 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) # needs sage.combinat 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 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: # needs sage.combinat 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 structure on the set of interval-posets.
The comparison is first by size, then using the cubical coordinates.
See also
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) False sage: TamariIntervalPosets().le(ip2,ip1) True
- options = Current options for TamariIntervalPosets - latex_color_decreasing: red - latex_color_increasing: blue - latex_hspace: 1 - latex_line_width_scalar: 0.5 - latex_tikz_scale: 1 - latex_vspace: 1#
- static recomposition_from_triple(left, right, r)#
Recompose an interval-poset from a triple (
left
,right
,r
).For the inverse method, see
TamariIntervalPoset.decomposition_to_triple()
.INPUT:
left
– an interval-posetright
– an interval-posetr
– the parameter of the decomposition, an integer
OUTPUT: an interval-poset
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:
DisjointUnionEnumeratedSets
,TamariIntervalPosets
The enumerated set of all Tamari interval-posets.
- 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:
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 [Cha2008]:
\[\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()#
- 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: # needs sage.combinat 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