Program

Combinatorics is one of the fastest growing areas in contemporary Mathematics, and much of this growth is due to the connections and interactions with other areas of Mathematics. This program is devoted to the very vibrant and active area of interaction between Combinatorics with Geometry and Topology. That is, we focus on (1) the study of the combinatorial properties or structure of geometric and topological objects and (2) the development of geometric and topological techniques to answer combinatorial problems. Key examples of geometric objects with intricate combinatorial structure are point configurations and matroids, hyperplane and subspace arrangements, polytopes and polyhedra, lattices, convex bodies, and sphere packings. Examples of topology in action answering combinatorial challenges are the by now classical Lovász’s solution of the Kneser conjecture, which yielded functorial approaches to graph coloring, and the  more recent, extensive topological machinery leading to breakthroughs on Tverberg-type problems. As specific topics that should be addressed during the semester we include the following: 1. Combinatorics of polytopes and cell complexes. One of the most prominent questions here is the "polynomial Hirsch Conjecture", that is, whether the diameter of the graph of a (simple) polytope is polynomial (or maybe even linear) in the number of vertices and dimension. There is also much yet to be done in our understanding of possible face numbers of various classes of simplicial complexes. For example, the so-called g-Conjecture is still not proven for all spheres, only for polytopes, and much is unknown about f-vectors of, for instance, balanced spheres/manifolds. Gradually there is also more and more attention beyond the simplicial case, e.g. on cubical complexes, general subdivisions, general polytopes, etc. Visibility complexes, Baues complexes, oriented matroids spaces and subspace arrangements are also studied for their topological properties  Finally, several topological arguments (e.g. from fixed-point theory) have proved useful in various discrete problems: construction of 0/1-polytopes with “many facets”, questions regarding lattice polytopes, or extremal properties of Minkowski sums, to name a few. 2. Topological methods in combinatorics and discrete geometry A number of classical problems from Convexity and Discrete Geometry can be translated, via the “Configuration Space/Test Map” scheme of Sarkaria and Živaljević, into topological questions about the existence of equivariant maps between certain spaces. The tools developed so far have led to recent substantial progress on several such problems, like the surprising disproof of the Topological Tverberg Theorem outside the prime power case. However, we feel some foundational work and re-evaluations of the machinery “beyond the Borsuk–Ulam Theorem” is greatly needed. Another very active area is the discretization of differential topological methods, leading to results on low-dimensional realization spaces of high-dimensional polytopes, new tools for the analysis of low-degree triangulations, unfolding of convex polytopes, or problems related to simplicial collapsibility such as Zeeman’s conjecture. Advanced tools such as discrete Morse theory, and Gromov-style metric geometry on complexes, are also starting to take a prominent place in topological combinatorics. 3. Geometric combinatorics in optimization and mathematical economics It is well-known that the combinatorics of convex sets and polyhedra is extremely relevant for algorithms and theory in optimization. A fast growing topic in this respect is the representability of polytopes as projections of low complexity polyhedra or spectrahedra (affine slice of a psd cone), motivated by the quest for faster algorithms for linear optimization over complicated polytopes. Yannakakis' seminal results for polytopes from 1991  have been generalized to lifts of convex sets in convex cones, relating for example the psd rank to sum-of-squares polynomials and semidefinite optimization. While the tools for this geometric problem come from many places, the topological obstructions to lifts have been largely unexplored, and many open problems remain. More recently, interesting connections have been established between variants of Sperner’s lemma to ‘fair division’ problems in mathematical economics. There are also natural connections of geometric combinatorics to voting theory: the space of preferences is often modeled as a line or a subset of Rn, but the preference sets often have natural geometrical or topological constraints (e.g., convex or connected), and a desired solution is often at the intersection of such sets. KKM and Helly-type theorems have found some nice applications in such problems, which in turn led to the development of new KKM and Helly-type theorems. 4. Algebraic and algebro-geometric methods. Ideas of algebraic geometry and Hopf algebras have been extremely useful to study f-vectors (and flag vectors) of convex polytopes and spheres, all starting from the famous proof of the g-theorem and its generalizations. Toric varieties, algebraic varieties that come with a “polyhedral dictionary” to read off algebraic invariants, have played an important role in this. Major progress has been made in understanding their properties and applying them to problems in commutative algebra via Gröbner bases and their relations to secondary and state polytopes.  Even more sophisticated algebro-geometric methods such as intersection theory of toric varietites and tropical intersection theory are also part of a standard toolkit in combinatorics, together with related objects such as Bergman fans in tropical geometry, subvarieties of products of complex projective spaces, etc. Striking progress on long-standing problems related to log-concavity of sequences arising from matroids has been recently achieved using some of these methods. There are also exciting connections between representation theory and singularity theory to the problem of counting lattice points in polytopes. In addition, certain polytopes and oriented matroids with special structure have recently appeared in work on crystal bases, total positivity, and nonnegative Grassmannians. There is even a recently discovered tantalizing connection between these non-negative Grassmannians, positroids, and certain physical theories, appearing in the literature under the rubric ‘amplituhedron’. In a different direction, dramatic breakthroughs in Erdős-type problems involving incidences between points and curves, distances in point sets, and k-sets, have been recently achieved via tools from algebraic geometry. Realization spaces also relate polytopes and arrangements to semi-algebraic geometry, and several universality theorems on them have been proved. Bibliography (PDF)