Mathematics – Combinatorics
Scientific paper
2007-04-27
Journal of Combinatorial Theory Series A 116, 1 (2009) 55-75
Mathematics
Combinatorics
22 pages
Scientific paper
The Stanley lattice, Tamari lattice and Kreweras lattice are three remarkable orders defined on the set of Catalan objects of a given size. These lattices are ordered by inclusion: the Stanley lattice is an extension of the Tamari lattice which is an extension of the Kreweras lattice. The Stanley order can be defined on the set of Dyck paths of size $n$ as the relation of \emph{being above}. Hence, intervals in the Stanley lattice are pairs of non-crossing Dyck paths. In a former article, the second author defined a bijection $\Phi$ between pairs of non-crossing Dyck paths and the realizers of triangulations (or Schnyder woods). We give a simpler description of the bijection $\Phi$. Then, we study the restriction of $\Phi$ to Tamari's and Kreweras' intervals. We prove that $\Phi$ induces a bijection between Tamari intervals and minimal realizers. This gives a bijection between Tamari intervals and triangulations. We also prove that $\Phi$ induces a bijection between Kreweras intervals and the (unique) realizers of stack triangulations. Thus, $\Phi$ induces a bijection between Kreweras intervals and stack triangulations which are known to be in bijection with ternary trees.
Bernardi Olivier
Bonichon Nicolas
No associations
LandOfFree
Catalan's intervals and realizers of triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Catalan's intervals and realizers of triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Catalan's intervals and realizers of triangulations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-677448