You are here

Non-realizability of polytopes via linear programming

Amy Wiebe, Simon Fraser University
Wednesday, February 2, 2022 - 3:30pm to 5:00pm
PDL C-38 and via Zoom Link:
Amy Wiebe
Amy Wiebe


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. In 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 polynomial 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.

Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.

Join Zoom Meeting:
Meeting ID: 915 4733 5974