DOCTORAL DEFENSE
"Structural and enumerative properties of k-triangulations of the n-gon."

Carlos Nicolas
University of Kentucky

Thursday, July 3, 2008
10:00 am, 845 Patterson Office Tower

Abstract:

A k-triangulation of the n-gon is a maximal set of diagonals of the n-gon such that no k+1 of them cross each other. The case k=1 coincides with the usual triangulations of the n-gon, and some of their properties have been known to hold for the general case. In this talk, I will recount these properties and prove a few more that I found. In 2004, Jonsson showed that the number of k-triangulations of the n-gon is given by a Hankel determinant of Catalan numbers. This determinant also counts the number of k non-crossing Dyck paths of size n-2k. A combinatorial bijection between these two sets is known only for the cases k=1 and k=2. I will construct a bijection for the case k=2 that preserves two pairs of parameters which are natural to these objects. As a consequence I obtain a refinement, which involves Catalan and ballot numbers, of the formula for the number of 2-triangulations. I will make some conjectures for the general case.