generalised Tamari lattices

[chapoton]

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

[hthomas]

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

[chapoton]

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 ?

[hthomas]

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

[chapoton]

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

[stumpc5]

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

[chapoton]

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

[hthomas]

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