Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A {em triangulation} of a finite point set $AsubsetR^d$ is a geometric simplicial complex which covers the convex hull of $A$ and whose vertices are elements of $A$. Triangulations of point sets have attracted special attention in recent years because of their connections to several fields of theoretical and applied mathematics as computational algebra and geometry, graph theory, polytope theory, optimization or computer aided geometric design. Although a considerable effort has been devoted to understand the structure of the set of triangulations of a point set in both the combinatorial and the topological sceneries, our knowledge on this topic is still widely incomplete.

The standard approaches study the set of triangulations via the so-called {em Baues poset} of $A$ or via the {em graph of triangulations} of $A$. The Baues poset is defined to be the set of all {em polyhedral subdivisions} of $A$ (i.e. the natural generalization of triangulations when we allow convex polyhedra instead of simplices) ordered by refinement. As usual, when we talk about the topology of a poset, we refer to that of its {em order complex}, which is a simplicial complex naturally associated to it. The graph of triangulations is the graph whose vertices are the triangulations and whose edges represent {em flips} between them (which are certain local ``simple moves" which transform one triangulation into another).

A triangulation (or subdivision) is {em regular} if can be obtained as the projection of the lower envelope of a ($d+1$)-polytope. When one restricts itself to regular subdivisions, the associated subposet and subgraph turn out to have very nice topologies; those of the ($k-1$)-skeleton and the $1$-skeleton of a particular $k$-polytope, for certain $k$, respectively. But, unfortunately, not every subdivision or triangulation is regular, moreover, regular triangulations tend to be sporadic compared with the What are then the topologies of these two spaces? The so-called {em Generalized Baues Conjecture} posed by Billera and Sturmfels claims, as a particular case, that the Baues poset has the homotopy type of a ($k-1$)-sphere, but what about the graph? Is it connected? Balinski's Theorem implies that the subgraph of regular triangulations is $k$-connected. Is the whole graph $k$-connected too? On the other hand, even the number of triangulations of a point set seems to be a difficult challenge.

We intend to give an overview of the known answers to these questions and to present a tool which has provided some of them recently. Namely, {em Gale duality}, which allows us to transform the study of a point set of size $n$ in $R^d$ to that of a vector configuration of size $n$ in $R^{n-d-1}$, and hence, turns out to be very useful when $n-d$ is small. We will therefore focus on the dualization of the notion of triangulation; the concept of {em virtual chamber}.