Opened 8 years ago
Closed 8 years ago
#13077 closed enhancement (fixed)
generalised Tamari lattices
Reported by: | chapoton | Owned by: | sage-combinat |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.7 |
Component: | combinatorics | Keywords: | poset |
Cc: | stumpc5 | Merged in: | sage-5.7.beta2 |
Authors: | Frédéric Chapoton | Reviewers: | Christian Stump, Hugh Thomas |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The Tamari lattice is a partial order on planar binary trees or Dyck paths.
(see Tamari Lattice in Wikipedia)
It has been generalized recently by F. Bergeron and his collaborators.
The patch below implements these lattices, and even more general versions.
apply trac_13077_tamari_posets-fc.patch
Attachments (1)
Change History (18)
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
comment:3 Changed 8 years ago by
- Description modified (diff)
comment:4 Changed 8 years ago by
- Summary changed from generalised Tamari posets to generalised Tamari lattices
comment:5 Changed 8 years ago by
- Milestone changed from sage-5.1 to sage-5.2
comment:6 Changed 8 years ago by
- Milestone changed from sage-5.2 to sage-5.3
- Priority changed from major to minor
comment:7 Changed 8 years ago by
comment:8 Changed 8 years ago by
Hello Hugh,
thanks for having a look at that.
I have added a few tests in the new version of the patch. In particular, one checks that (i,j) is in the correct half-rectangle.
In these lattices, m is really another independant parameter, having nothing to do with a/b. It would not make sense here to make m a rational number. Morally, m is the quotient of the lengths of vertical and horizontal steps, which defines a hidden notion of diagonal, which is used in "swap" to define the coverings.
I understand that I would be much better if these lattices are described somewhere. So far, they do not appear in print.
Do you think it is neccessary to explain in the patch why they are indeed lattices ?
comment:9 Changed 8 years ago by
Salut Frédéric--
On the contrary, I think it does make sense to have m be rational (independent of a and b), not just integral. But, fine, that can be a discussion for another time (or another ticket).
I think the patch should include some mathematical reference. Maybe the paper I mentioned above by Bousquet-Mélou--Fusy--Préville-Ratelle. That shows the m-Tamari poset is a lattice, and it's not very far from that to the general (a,b) case, right? (Since the (a,b,m) case occurs as an interval in the m-Tamari.) I don't think it's necessary to include a reference for every relevant mathematical fact, of course, but I think it could be helpful for someone who stumbles across this code to be able to find some further information and context.
Speaking of which, I'm wondering how a user is supposed to find this code. (I guess this is a perennial problem with Sage.) I suppose a user can always search the manual (or the code). I wish there was some alternative that would make it slightly easier to find things. Do you have any idea? Is there somewhere in the posets documentation that lists implemented posets? This seems like something which it might be worthwhile to have.
I'm a bit surprised about the way "swap" reacts if it is given a legal string, and a position within the string, at which it is not possible to do a swap (namely: return the same string as the answer). To me, it seems natural to raise an error. If you like it better not to do so, though, I think that behaviour should be documented.
cheers,
Hugh
comment:10 Changed 8 years ago by
Here is a new patch
- I have added the reference to BMFPR
- I have changed the behaviour of swap, now raising an error when no move is possible
- I have added a link to wikipedia article on Tamari lattice
Fred
comment:11 follow-up: ↓ 12 Changed 8 years ago by
- Cc stumpc5 added
comment:12 in reply to: ↑ 11 Changed 8 years ago by
Replying to chapoton:
Hi Fred,
I attached a review patch containing several improvements (hopefully) for the doc strings. Beside that, I think the patch is ready to go. I though have two remaining questions:
- I think you should mention that the generalised Tamari lattice is only conjectured to be a lattice (there is at least no publicly available source of a proof).
- You are mixing British English ("nonnegative") and American English ("generalised"): I think it would be nice to make this consistent, and to actually check if "generalised/generalized" is already used in other placed in Sage to keep consistency here.
Cheers, Christian
Changed 8 years ago by
comment:13 Changed 8 years ago by
- Description modified (diff)
I have replaced generalised by generalized
I have added a note on the conjectural status of lattice property
apply trac_13077_tamari_posets-fc.patch
comment:14 Changed 8 years ago by
Hi Frédéric and Christian--
Sorry not to have got around to finishing refereeing this, and I'm glad Christian has instead.
Christian, these (a,b,m) lattices are clearly intervals inside the m-Tamari. So they are lattices. For that reason I wouldn't say that the lattice property is conjectural, and I'm happy with what Frédéric wrote originally. (But I don't mean to delay a positive review over this.)
cheers,
Hugh
comment:15 Changed 8 years ago by
- Reviewers set to Christian Stump, Hugh Thomas
- Status changed from needs_review to positive_review
comment:16 Changed 8 years ago by
- Milestone changed from sage-5.6 to sage-5.7
comment:17 Changed 8 years ago by
- Merged in set to sage-5.7.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
Salut Frédéric--
A couple of thoughts. Maybe paths_in_triangle should take a parameter "slope" instead of a,b? Alternatively, I think the code should check that (i,j) is actually in the rectangle between (0,0) and (a,b).
In the definition of "swap", the code as written requires m to be an integer, but why do it like that? For arbitrary relatively prime a,b, I think a/b is a natural choice of parameter. This matches the "rational Catalan combinatorics" (see the two sets of Rational Catalan Combinatorics slides at Drew Armstrong's website http://www.math.miami.edu/~armstrong/research.html). One downside to the further generality is that I don't know whether or not it's a lattice. But I don't think that's really an argument against implementing it. Maybe an appropriate analogue of Bousquet-Mélou--Fusy--Préville-Ratelle, arXiv:1106.1498, Proposition 4 holds? But a glance, it wasn't obvious to me that it would.
I also think it would be good to include a reference for the generalized Tamari lattice in the documentation (and/or a more complete definition).
cheers,
Hugh