Intervals in Catalan lattices and realizers of triangulations (Q1003621): Difference between revisions

The paper is concerned with the Stanley, Tamari, and Kreweras lattices -- three orders on Dyck paths. The realizer of a planar triangulation, or Schnyder wood (cf.\ [\textit{W. Schnyder}, ``Planar graphs and poset dimension'', Order 5, No.~4, 323--343 (1989; Zbl 0675.06001), ``Embedding planar graphs on the grid'', in: A. Agarwal (ed.), Discrete algorithms. Proceedings of the 1st annual ACM-SIAM symposium, held January 22--24, 1990 in San Francisco, CA (USA). Philadelphia, PA (USA): SIAM. 138--148 (1990; Zbl 0786.05029)]), is a type of 3-colouring of the internal edges of a planar triangulation. In an earlier paper [\textit{N. Bonichon}, ``A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths'', Discrete Math. 298, No.~1--3, 104--114 (2005; Zbl 1070.05032)], the second author defined a bijection \(\Phi\) between pairs of non-crossing Dyck paths and the realizers of triangulations. From the authors' abstract: ``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 ternary trees.''