Title

Combinatorial Polynomial Hirsch Conjecture

Graduation Year

2017

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science

Department

Mathematics

Reader 1

Mohamed Omar

Reader 2

Nicholas Pippenger

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

© 2017 Sam K Miller

Abstract

The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the Combinatorial Polynomial Hirsch Conjecture, which turns the problem into a matter of counting sets.

This thesis explores the Combinatorial Polynomial Hirsch Conjecture.