From generalized Tamari intervals to non-separable planar maps

Let v be a grid path made of north and east steps. The lattice TAM(v), based on all grid paths weakly above the grid path v sharing the same endpoints as v, was introduced by Pre ́ville-Ratelle and Viennot (2014) and corresponds to the usual Tamari lattice in the case v = (NE)n. They showed that TAM...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2020-04, Vol.DMTCS Proceedings, 28th...
Main Authors: Fang, Wenjie, Préville-Ratelle, Louis-François
Format: Article
Language:English
Subjects:
[math.math-co]mathematics [math]/combinatorics [math.co]
Combinatorics
Mathematics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let v be a grid path made of north and east steps. The lattice TAM(v), based on all grid paths weakly above the grid path v sharing the same endpoints as v, was introduced by Pre ́ville-Ratelle and Viennot (2014) and corresponds to the usual Tamari lattice in the case v = (NE)n. They showed that TAM(v) is isomorphic to the dual of TAM(←−v ), where ←−v is the reverse of v with N and E exchanged. Our main contribution is a bijection from intervals in TAM(v) to non-separable planar maps. It follows that the number of intervals in TAM(v) over all v of length n is 2(3n+3)! (n+2)!(2n+3)! . This formula was first obtained by Tutte(1963) for non-separable planar maps.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.6421