Speaker: Walter Morris, George Mason University
Date and time: Thursday, September 20, 4–5 pm
Location: Phillips 110
Abstract: The strict monotone d-step conjecture for linear programming says that, given a d-dimensional polytope P with 2d facets and a linear function f, there is a path in the graph of P from the vertex with minimum f value to the vertex with maximum f value that is increasing in f and contains at most d edges. Santos (2012) showed that this conjecture is false for d sufficiently large, but the largest d for which it is true is not known. For d = 5 we created a logical statement that is unsatisfiable if there is no counterexample. The satisfiablility solver that we used showed that there is no counterexample.