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 the left_to_right variable set to False) 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.