Intervals in Catalan lattices and realizers of triangulations

DOI10.1016/J.JCTA.2008.05.005zbMATH Open1161.06001arXiv0704.3731OpenAlexW1971351183MaRDI QIDQ1003621FDOQ1003621

Olivier Bernardi, Nicolas Bonichon

Publication date: 4 March 2009

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0704.3731

zbMATH Keywords

triangulationsbijectionTamari latticeSchnyder woodKreweras latticeStanley lattice

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Combinatorics of partially ordered sets (06A07) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Binomial determinants, paths, and hook length formulae
• Planar graphs and poset dimension
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• Noncrossing partitions
• Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law
• Noncrossing Partitions in Surprising Locations
• A Census of Planar Triangulations
• Realization of the Stasheff polytope
• Multichains, non-crossing partitions and trees
• A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths

Cited In (60)

• Mating of discrete trees and walks in the quarter-plane
• Some properties of a new partial order on Dyck paths
• Recursive constructions for the higher Stasheff-Tamari orders in dimension three using the outer Tamari and Tamari block posets
• Bijections for Baxter families and related objects
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Unified bijections for maps with prescribed degrees and girth
• Unitarily invariant valuations and Tutte’s sequence
• Bijective counting of plane bipolar orientations
• Title not available (Why is that?)
• Three Fuss-Catalan posets in interaction and their associative algebras
• Planar triangulations, bridgeless planar maps and Tamari intervals
• The Tamari block lattice: an order on saturated chains in the Tamari lattice
• Model structures on finite total orders
• Enumeration of corner polyhedra and 3-connected Schnyder labelings
• Enumeration of corner polyhedra and 3-connected Schnyder labelings
• The pruning-grafting lattice of binary trees
• The rank enumeration of certain parabolic non-crossing partitions
• Precision measurements of Hausdorff dimensions in two-dimensional quantum gravity
• Une note sur les intervalles de Tamari
• The rise-contact involution on Tamari intervals
• Cambrian triangulations and their tropical realizations
• A partial order on Motzkin paths
• Cubic realizations of Tamari interval lattices
• Chains of maximum length in the Tamari lattice
• On the number of planar Eulerian orientations
• Intervals of balanced binary trees in the Tamari lattice
• Orienting triangulations
• Enumeration of chains and saturated chains in Dyck lattices.
• Modular Fuss-Catalan numbers
• On the Categories of Modules Over the Tamari Posets
• Bijective link between Chapoton's new intervals and bipartite planar maps
• The enumeration of generalized Tamari intervals
• Exceptional and modern intervals of the Tamari lattice
• Schnyder decompositions for regular plane graphs and application to drawing
• Geometric realizations of Tamari interval lattices via cubic coordinates
• Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods
• Bijections for walks ending on an axis, using open arc diagrams
• A mating-of-trees approach for graph distances in random planar maps
• Symmetries of unlabelled planar triangulations
• A trinity of duality: non-separable planar maps, \(\beta(1,0)\)-trees and synchronized intervals
• Celebrating Loday's associahedron
• Bijective counting of plane bipolar orientations and Schnyder woods
• A recursion on maximal chains in the Tamari lattices
• The generating function of planar Eulerian orientations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Uniquely sorted permutations
• Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators
• The representation of the symmetric group on \(m\)-Tamari intervals
• Further bijections to pattern-avoiding valid hook configurations
• Catalan intervals and uniquely sorted permutations
• Schnyder woods, \(\mathrm{SLE}_{16}\), and Liouville quantum gravity
• On the enumeration of plane bipolar posets and transversal structures
• A catalanization map on the symmetric group
• Intervals in the greedy Tamari posets
• Bijections for generalized Tamari intervals via orientations
• Bijections for generalized Tamari intervals via orientations
• Composition closed premodel structures and the Kreweras lattice
• What is a random surface?
• The combinatorics of a tree-like functional equation for connected chord diagrams

This page was built for publication: Intervals in Catalan lattices and realizers of triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003621)