Polyhedral Combinatorics

Polyhedral combinatorics deals with the application of various aspects of the theory of polyhedra and linear systems to combinatorics. Over the past thirty years a great many researchers have shown how a large number of polyhedral concepts and results have elegant combinatorial consequences. Here, however, we concentrate our attention on developments over the last ten years. We survey the relationship between linear systems which define a polyhedron and combinatorial min-max theorems obtained via linear programming duality. We discuss two methods of improving these theorems, first by reducing the number of dual variables (facet characterizations) and second, by requiring that dual variables take on integer values (total unimodularity and total dual integrality). One consequence of the ellipsoid algorithm for linear programming has been to show the equivalence of optimization and separation (determining whether or not a given point belongs to a polyhedron, and if not, finding a separating hyperplane). We discuss the theoretical importance of this as well as several instances where in this approach was used to solve successfully “real world” optimization problems (before the development of the ellipsoid method). Finally, we briefly discuss the concepts of adjacency and dimension, both of which recently have been shown to have interesting combinatorial consequences.