You are here

Non-realizability of polytopes via linear programming

Event Category:
Discrete Math Seminar
Amy Wiebe
Simon Fraser University

A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. The method of “final polynomials” introduced by Bokowski and Sturmfels, is often exploited to answer this question in the negative for specific instances. It involves finding a polynomial which, based on the structure of your polytope if realizable, must be simultaneously zero and positive, a clear contradiction. The search space for certificates of non-realizability based on this technique is the ideal of Grassman-Plücker relations. Most instances where this technique has been used, additional assumptions on the structure of the desired polynomial are necessary as the search space quickly becomes too large to search by brute force. In this talk, I will describe how by changing the search space, we are able to use linear programming to exhaustively search for similar polynomials certificates without any assumed structure. We will see that perhaps surprisingly, this elementary strategy yields results that are competitive with more elaborate alternatives, and allows us to prove non-realizability of several interesting polytopes.

Friday, February 11, 2022 - 10:00am
LGRT 1634 and on zoom