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.
TamariIntervalPoset
¶ 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 []
-
sage.combinat.interval_posets.
TamariIntervalPosets
¶ 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.
-
sage.combinat.interval_posets.
TamariIntervalPosets_all
¶ The enumerated set of all Tamari interval-posets.
-
sage.combinat.interval_posets.
TamariIntervalPosets_size
¶ The enumerated set of interval-posets of a given size.