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] | Gregory Chatel and Viviane Pons. Counting smaller trees in the Tamari order. FPSAC. (2013). Arxiv 1212.0751v1. |
[Pons2013] | Viviane Pons, Combinatoire algebrique liee 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) Frederic Chapoton. Sur le nombre d’intervalles dans les treillis de Tamari. Sem. Lothar. Combin. (2008). Arxiv math/0602368v1. |
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
, with labels
, satisfying the following conditions:
- if
(as integers) and
precedes
in the poset, then, for all
such that
,
precedes
,
- if
(as integers) and
precedes
in the poset, then, for all
such that
,
precedes
.
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
are in bijection with intervals of the Tamari lattice of binary trees of size
. Specifically, if
is an interval-poset of size
, then the set of linear extensions of
(as permutations in
) 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) 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 ‘precedes
‘ 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
mean the pairs
of elements of
such that
as integers and
precedes
in
. The initial forest of
is the poset obtained by imposing (only) the increasing relations on the ground set of
. It is a sub-interval poset of
, 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
in this order.
The decreasing relations of an interval-poset
mean the pairs
of elements of
such that
as integers and
precedes
in
. The final forest of
is the poset obtained by imposing (only) the decreasing relations on the ground set of
. It is a sub-interval poset of
, 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 arein 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
is a Tamari interval-poset of size
, then the complement of
is defined as the interval-poset
whose base set is
(just as for
), but whose order relation has
precede
if and only if
precedes
in
.
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 formprecedes
with
).
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!) vertexsuch that
v
precedesa
. If there is no such vertex (that is,is a decreasing 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.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 verticessuch that there is no
with
preceding
.
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 formprecedes
with
).
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
such that
precedes
. If there is no such vertex (that is,
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 verticesof
self
such that there is nowith
precedes
.
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
into the interval-poset
self
.If
is a Tamari interval-poset of size
and
is an integer with
, then the Tamari insertion of
into
is defined as the Tamari interval-poset of size
which corresponds to the interval
on the Tamari lattice, where the binary trees
and
are defined as follows: We write the interval-poset
as
for two binary trees
and
. We label the vertices of each of these two trees with the integers
in such a way that the trees are binary search trees (this labelling is unique). Then, we insert
into each of these trees (in the way as explained in
binary_search_insert()
). The shapes of the resulting two trees are denotedand
.
An alternative way to construct the insertion of
into
is by relabeling each vertex
of
satisfying
(as integers) as
, and then adding a vertex
which should precede
and
.
Todo
To study this, it would be more natural to define interval-posets on arbitrary ordered sets rather than just on
.
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_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_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].
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
-
latex_options
()¶ Return the latex options for use in the
_latex_
function as a dictionary. The default values are set using the global 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 intervalof the Tamari lattice, return an iterator on all intervals
with
for the Tamari lattice.
In terms of interval-posets, it corresponds to adding all possible relations of the form
precedes
with
.
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 intervalof the Tamari lattice, this returns intervals
with
following one longest chain between
and
.
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 relationsfrom each Tamari inversion
to
self
, 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]
-
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
-
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 global 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.global_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 does not override it:
sage: ip.set_latex_options({"color_decreasing": 'black'}) sage: ip.latex_options()["color_decreasing"] 'black' sage: TamariIntervalPosets.global_options(latex_color_decreasing='blue') sage: ip.latex_options()["color_decreasing"] 'black' sage: ip2.latex_options()["color_decreasing"] 'blue' sage: TamariIntervalPosets.global_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
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 verticeswith
such that:
- the decreasing parent of
is strictly smaller than
(or does not exist), and
- the increasing parent of
is strictly bigger than
(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
is a proper subset of a Tamari interval
, then the inversion number of
is strictly lower than the inversion number of
. And finally, by adding the relation
to the interval-poset where
is the first inversion of
in lexicographic order, one reduces the inversion number by exactly
.
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
- the decreasing parent of
-
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
- if
-
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
where
is its size.
- If
(as numbers) and
precedes
, then
precedes
for all
such that
.
- If
(as numbers) and
precedes
, then
precedes
for all
such that
.
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
- Its labels are exactly
-
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:
precedes
in the final forest iff
is in the right subtree of
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 nottree2
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
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.
-
global_options
(*get_value, **set_value)¶ Set and display the global 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.global_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.global_options(latex_color_decreasing='green') sage: ip.latex_options()["color_decreasing"] 'green' sage: TamariIntervalPosets.global_options.reset() sage: ip.latex_options()["color_decreasing"] 'red'
See
GlobalOptions
for more features of these options.
-
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:
precedes
in the initial forest iff
is in the left subtree of
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
-
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.
TESTS:
sage: from sage.combinat.interval_posets import TamariIntervalPosets_size sage: for i in xrange(6): TestSuite(TamariIntervalPosets_size(i)).run()
-
cardinality
()¶ The cardinality of
self
. That is, the number of interval-posets of size.
The formula was given in [ChapTamari08]:
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
-