Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Project: Public Code
Views: 18
%html <h3> Code demonstration for Tamari interval-posets in Sage </h3> <p> This code is related to the paper:<br /> [1] Grégory Châtel and Viviane Pons. <a href="http://arxiv.org/abs/1311.3922">Counting smaller elements in the Tamari and m-Tamari lattices</a>, to appear in Journal of Combinatorial Theory, Series A. </p>

Code demonstration for Tamari interval-posets in Sage

This code is related to the paper:
[1] Grégory Châtel and Viviane Pons. Counting smaller elements in the Tamari and m-Tamari lattices, to appear in Journal of Combinatorial Theory, Series A.

Creating an interval-poset.

def latex_view(obj): return latex.eval(latex(obj))
ip = TamariIntervalPoset(4,[(2,1),(3,1),(2,4),(3,4)]); ip
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)]
latex_view(ip)
''

Creating from a binary tree or a Dyck path.

bt1 = BinaryTree([[None, [[], None]], None]) bt2 = BinaryTree([None, [[None, []], None]]) ip = TamariIntervalPosets.from_binary_trees(bt1,bt2) ip
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)]
ip = bt1.tamari_interval(bt2) ip
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)]
dw1 = DyckWord([1, 1, 0, 1, 0, 0, 1, 0]) dw2 = DyckWord([1, 1, 1, 0, 0, 1, 0, 0]) ip = TamariIntervalPosets.from_dyck_words(dw1,dw2) ip
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)]
ip = dw1.tamari_interval(dw2) ip
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)]

Computing its endpoints as binary trees and list the binary trees of the interval.

ip.lower_binary_tree() ip.upper_binary_tree()
[[., [[., .], .]], .] [., [[., [., .]], .]]
latex_view(ip.lower_binary_tree()) latex_view(ip.upper_binary_tree())
''
''
for bt in ip.binary_trees(): bt
[., [[., [., .]], .]] [[., [., [., .]]], .] [., [[[., .], .], .]] [[., [[., .], .]], .]
Computing its end points as Dyck paths and list the Dyck path of the interval.
ip.lower_dyck_word() ip.upper_dyck_word()
[1, 1, 0, 1, 0, 0, 1, 0] [1, 1, 1, 0, 0, 1, 0, 0]
for dw in ip.dyck_words(): dw
[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]

In [1], we define a composition of interval-posets. Below are the methods corresponding to this composition.

def left_product(ip1,ip2): size = ip1.size() + ip2.size() # Juxtaposition of ip1 and shifted ip2 relations = list(ip1._cover_relations) + [(i+ip1.size(),j+ip1.size()) for (i,j) in ip2._cover_relations] # Increasing relations between ip1 and the first vertex of ip2 relations+= [(i,ip1.size()+1) for i in ip1.increasing_roots()] return TamariIntervalPoset(size,relations) def right_product(ip1, ip2): size = ip1.size() + ip2.size() # Juxtaposition of ip1 and shifted ip2 relations = list(ip1._cover_relations) + [(i+ip1.size(),j+ip1.size()) for (i,j) in ip2._cover_relations] # First element: no extra decreasing relation yield TamariIntervalPoset(size,relations) for j in ip2.decreasing_roots(): # Adding decreasing relations 1 by 1 relations.append((j+ip1.size(),ip1.size())) yield TamariIntervalPoset(size,relations) def composition(ip1,ip2): u = TamariIntervalPoset(1,[]) left = left_product(ip1,u) for r in right_product(left,ip2): yield r
Here is an example of computation that corresponds to Figure 13 of [1].
ip1 = TamariIntervalPoset(3,[(1,2),(3,2)]) ip2 = TamariIntervalPoset(4,[(2,3),(4,3)]) r = list(composition(ip1,ip2)) r
[The tamari interval of size 8 induced by relations [(1, 2), (2, 4), (3, 4), (6, 7), (8, 7), (3, 2)], The tamari interval of size 8 induced by relations [(1, 2), (2, 4), (3, 4), (6, 7), (8, 7), (5, 4), (3, 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)], The tamari interval of size 8 induced by relations [(1, 2), (2, 4), (3, 4), (6, 7), (8, 7), (7, 4), (6, 4), (5, 4), (3, 2)]]
for ipr in r: latex_view(ipr)
''
''
''
''
There is also a mm-composition defined in [1] which is implemented below.
def right_product_dim(ip1,ip2): size = ip1.size() + ip2.size() # Juxtaposition of ip1 and shifted ip2 relations = list(ip1._cover_relations) + [(i+ip1.size(),j+ip1.size()) for (i,j) in ip2._cover_relations] for j in ip2.decreasing_roots(): # Adding decreasing relations 1 by 1 relations.append((j+ip1.size(),ip1.size())) yield TamariIntervalPoset(size,relations) def mcomposition(ips): rights = ips[1:] # we take the list of intervals excpect the first one def compute_rights(rights): # we define a recursive method to compute the right part u = TamariIntervalPoset(1,[]) if len(rights)==1: for r in right_product(u,rights[0]): yield r else: for r1 in compute_rights(rights[1:]): r1 = left_product(r1,rights[0]) for r2 in right_product_dim(u,r1): yield r2 for r in compute_rights(rights): yield left_product(ips[0],r)

Here is an example corresponding to (4.16) of [1].

ip1 = TamariIntervalPoset(2,[(2,1)]) ip2 = TamariIntervalPoset(4,[(2,1),(4,3),(2,3)]) ip3 = ip1 r = list(mcomposition([ip1,ip2,ip3])) r
[The tamari interval of size 10 induced by relations [(1, 3), (2, 3), (4, 7), (5, 7), (6, 7), (8, 9), (10, 9), (8, 7), (6, 5), (4, 3), (2, 1)], The tamari interval of size 10 induced by relations [(1, 3), (2, 3), (4, 7), (5, 7), (6, 7), (8, 9), (10, 9), (8, 7), (6, 5), (5, 3), (4, 3), (2, 1)], The tamari interval of size 10 induced by relations [(1, 3), (2, 3), (4, 7), (5, 7), (6, 7), (8, 9), (10, 9), (8, 7), (7, 3), (6, 5), (5, 3), (4, 3), (2, 1)], The tamari interval of size 10 induced by relations [(1, 3), (2, 3), (4, 7), (5, 7), (6, 7), (8, 9), (10, 9), (9, 3), (8, 7), (7, 3), (6, 5), (5, 3), (4, 3), (2, 1)], The tamari interval of size 10 induced by relations [(1, 3), (2, 3), (4, 7), (5, 7), (6, 7), (8, 9), (10, 9), (8, 7), (6, 5), (5, 4), (4, 3), (2, 1)], The tamari interval of size 10 induced by relations [(1, 3), (2, 3), (4, 7), (5, 7), (6, 7), (8, 9), (10, 9), (8, 7), (7, 3), (6, 5), (5, 4), (4, 3), (2, 1)], The tamari interval of size 10 induced by relations [(1, 3), (2, 3), (4, 7), (5, 7), (6, 7), (8, 9), (10, 9), (9, 3), (8, 7), (7, 3), (6, 5), (5, 4), (4, 3), (2, 1)]]
for ipr in r: latex_view(ipr)
''
''
''
''
''
''
''