Laboratoire d'informatique de l'École polytechnique

Talk by Manuel Wettstein: «Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers»

Speaker: Manuel Wettstein (ETH Zürich)
Location: Room Philippe Flajolet, Alan Turing building
Date: Wed, 7 Dec 2016, 11:00-12:00

Abstract: We introduce the notion of a trapezoidal diagram of a plane straight-line graph G. Loosely speaking, such a diagram encodes the vertical visibility relations between edges and vertices of G. We study the number of such diagrams if the graphs G are either (a) perfect matchings or (b) triangulations. We give bijections to (a) 3-dimensional balanced bracket expressions and (b) a subset of indecomposable such expressions. While the former corresponds to a well-known 3-dimensional generalization of Catalan numbers, the latter gives rise to a previously unknown integer sequence which we call prime Catalan numbers. Exponential growth rates of both sequences can then be determined. A connection between the resulting diagrams (b) and so called upward triangulations will be discussed briefly.