## 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.