Intervals in Catalan lattices and realizers of triangulations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:116

Article

Bernardi, Olivier¹  Bonichon, Nicolas² 

[1] Univ Paris 11, Math Lab, F-91405 Orsay, France

[2] LaBRI, F-33405 Talence, France

关键词: Tamari lattice;    Kreweras lattice;    Stanley lattice;    Schnyder woods;    Triangulations;    Bijection;   

DOI  :  10.1016/j.jcta.2008.05.005

来源: Elsevier

【 摘 要 】

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 being above. Hence, intervals in the Stanley lattice are pairs of non-crossing Dyck paths. In a previous 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 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 tertiary trees. (C) 2008 Elsevier Inc. All rights reserved.

【 授权许可】

Free