#15683: Interval-posets of Tamari
-------------------------------------+-------------------------------------
Reporter: VivianePons | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.2
Component: combinatorics | Resolution:
Keywords: combinat, Tamari, | Merged in:
binary trees, Dyck paths | Reviewers:
Authors: Viviane Pons | Work issues: make import lazy,
Report Upstream: N/A | review
Branch: public/combinat | Commit:
/interval-posets-15683 | 058d7bf6c7c9aba92fef6fd9b0648e5db05fcfaa
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by darij):
Sorry for the delays :/ I'm trying to get this done.
There is some reversal of permutations lurking somewhere in either the
code or the theory:
{{{
sage: p = Permutation([2,4,1,6,5,3])
sage: t = p.binary_search_tree(); t
2[1[., .], 4[3[., .], 6[5[., .], .]]]
sage: i = t.tamari_interval(t); i
The tamari interval of size 6 induced by relations [(1, 2), (3, 4), (5,
6), (6, 4), (5, 4), (4, 2), (3, 2)]
sage: lins = i.linear_extensions()
sage: list(lins)
[[5, 6, 3, 4, 1, 2],
[5, 6, 3, 1, 4, 2],
[5, 6, 1, 3, 4, 2],
[5, 3, 6, 4, 1, 2],
[5, 3, 6, 1, 4, 2],
[5, 3, 1, 6, 4, 2],
[5, 1, 6, 3, 4, 2],
[5, 1, 3, 6, 4, 2],
[3, 5, 6, 4, 1, 2],
[3, 5, 6, 1, 4, 2],
[3, 5, 1, 6, 4, 2],
[3, 1, 5, 6, 4, 2],
[1, 5, 6, 3, 4, 2],
[1, 5, 3, 6, 4, 2],
[1, 3, 5, 6, 4, 2]]
}}}
Actually, the problem seems to be in the trees code, and it's a bug
because it contradicts the doc:
{{{
sage: p = Permutation([2,4,1,6,5,3])
sage: b = p.binary_search_tree()
sage: [Permutation(a).binary_search_tree() for a in
b.sylvester_class()][1[., 3[2[., .], 5[4[., .], 6[., .]]]],
3[1[., 2[., .]], 5[4[., .], 6[., .]]],
3[1[., 2[., .]], 5[4[., .], 6[., .]]],
3[1[., 2[., .]], 5[4[., .], 6[., .]]],
3[1[., 2[., .]], 5[4[., .], 6[., .]]],
1[., 5[3[2[., .], 4[., .]], 6[., .]]],
5[1[., 3[2[., .], 4[., .]]], 6[., .]],
5[3[1[., 2[., .]], 4[., .]], 6[., .]],
5[3[1[., 2[., .]], 4[., .]], 6[., .]],
5[3[1[., 2[., .]], 4[., .]], 6[., .]],
1[., 5[3[2[., .], 4[., .]], 6[., .]]],
5[1[., 3[2[., .], 4[., .]]], 6[., .]],
5[1[., 3[2[., .], 4[., .]]], 6[., .]],
5[3[1[., 2[., .]], 4[., .]], 6[., .]],
5[3[1[., 2[., .]], 4[., .]], 6[., .]]]
sage: [Permutation(reversed(a)).binary_search_tree() for a in
b.sylvester_class()]
[2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]],
2[1[., .], 4[3[., .], 6[5[., .], .]]]]
}}}
What do we do about it? (I'm really hoping this doesn't reflect a conflict
in literature.)
--
Ticket URL: <http://trac.sagemath.org/ticket/15683#comment:29>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
