Combinatorial Analysis of Polytopes and Polyhedral Subdivisions – CAPPS

This project studies combinatorial problems on (possibly high dimensional) convex polytopes and polyhedral subdivisions. These arise naturally in several research areas in mathematics and computer science, both theoretical and applied. Although many of these problems are strongly related, they are traditionally formulated and approached from completely different points of view. We want to unveil and exploit such connections by sharing problems, techniques and perspectives from our different complementary backgrounds.

The range of topics we want to study covers different aspects of the field. They include doing a combinatorial analysis of geometric constructions as well as understanding geometric constraints imposed by combinatorial structures. We want to study enumeration problems for combinatorial types of polytopes, with a view to revealing typical properties of random combinatorial instances. We also want to explore applications and extensions of the theory of generalized Gale transforms for the operations of projection and section. We expect these advances to be relevant in the study of extended formulations, a very active topic in the combinatorial optimization community, but also in the context of shadow and stabbing problems, and in relation to the convex dimension of graphs. Finally, we want to investigate realizability problems on tropical polytopes and oriented matroids. These are motivated by applications of tropical linear programming as well as by the search of polyhedral realizations of combinatorial structures.