moteur de recherche

Séminaire Algo - Manuel Wettstein
Séminaire Algo - Manuel Wettstein
6-déc.-2016 14:30
Il y a: 1 year

Manuel Wettstein

Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers

Salle de séminaire (4B05R) - Bâtiment Copernic

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.

<- retour: