Universal constructors in polytopal graph theory

Polytopal graph theory is concerned with the graphs formed by the edges and vertices of polytopes. The graph of a simple polytope contains all of the necessary information to recover its full combinatorial structure in polynomial time, and thus is equivalent in a strong sense to the object.  

These objects are both mathematically and aesthetically beautiful as well as practically relevant.  




Properties of polytopal graphs are linked with a number of important algorithmic questions about polytopes such as the complexity of  linear programming and the convergence of randomized algorithms.

However, a number of fundamental combinatorial questions about polytopal graphs remain unresolved, including questions about the number, diameter, conductance and structure, and it is not always clear how these can be addressed. Polytopes have historically been understood with the help of several constructive operations, including wedging, one-point suspension, convex hulls, projections, subdivision, and related tools. 

In my research, I've proposed the use of a new set of operators on combinatorial polytopes, known as projective removal, combinatorial constraint perturbation, and combinatorial cutting planes. Unlike previously used operators, these operators are universal in the sense that any combinatorial type of simple polytope may be constructed from a simplex by applying a particular sequence of these operatiors. It is hoped that they can provide value in reasoning about polytopal graphs, since by showing that a given property of interest is preserved under these universal transformations, we necessarily establish that the property is true for all simple polytopes.

These operators are dual to a specific set of bistellar flips on simplicial spheres, meaning these techinques strengthen Pachner's theorem.  

The method may be useful in addressing problems on polytopal graphs. Three problems are of particular interest: polytope enumeration, the polytope diameter problems (polynomial Hirsch conjecture), and the Generalized Perles conjecture.

The polytope enumeration problem seeks an algorithm for enumeration of the combinatorial types of (n, d) polytopes and seeks to produce bounds on the number of (n, d) polytopes. Complete enumerations have been carried out only in several low dimensions.

The polynomial Hirsch conjecture seeks a polynomial bound on the diameter of polytopal graphs.

The Generalized Perles conjecture asks whether every connected, non-disconnecting 3-polytopal subgraph of a simple 4-polytopal graph corresponds  to the graph of a facet of the corresponding polytope.