Opened 8 years ago

Closed 7 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 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

Attachments (1)

trac_13077_tamari_posets-fc.patch (8.5 KB) - added by chapoton 7 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 8 years ago by chapoton

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by chapoton

  • Authors set to Frédéric Chapoton

comment:3 Changed 8 years ago by chapoton

  • Description modified (diff)

comment:4 Changed 8 years ago by chapoton

  • Summary changed from generalised Tamari posets to generalised Tamari lattices

comment:5 Changed 7 years ago by chapoton

  • Milestone changed from sage-5.1 to sage-5.2

comment:6 Changed 7 years ago by chapoton

  • Milestone changed from sage-5.2 to sage-5.3
  • Priority changed from major to minor

comment:7 Changed 7 years ago by 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

comment:8 Changed 7 years ago by 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 ?

comment:9 Changed 7 years ago by 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

comment:10 Changed 7 years ago by 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

comment:11 follow-up: Changed 7 years ago by chapoton

  • Cc stumpc5 added

comment:12 in reply to: ↑ 11 Changed 7 years ago by 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

Changed 7 years ago by chapoton

comment:13 Changed 7 years ago by chapoton

  • 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 7 years ago by 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

comment:15 Changed 7 years ago by stumpc5

  • Reviewers set to Christian Stump, Hugh Thomas
  • Status changed from needs_review to positive_review

comment:16 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.6 to sage-5.7

comment:17 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.7.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.