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
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.
Recommended Citation
Miller, Sam, "Combinatorial Polynomial Hirsch Conjecture" (2017). HMC Senior Theses. 109.
https://scholarship.claremont.edu/hmc_theses/109
Source Fulltext
https://www.math.hmc.edu/seniorthesis/archives/2017/smiller/smiller-2017-thesis.pdf
Included in
Discrete Mathematics and Combinatorics Commons, Other Mathematics Commons, Set Theory Commons, Theory and Algorithms Commons
