Combinatorics Seminar- A proof of the strict monotone 5-step conjecture

Speaker: Walter Morris, George Mason University
Date and time: Thursday, September 20, 4-5pm
Place:  Phillips 110
Title: A proof of the strict monotone 5-step conjecture
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.