Diameter of simplicial complexes, a computational approach.

Abstract

ABSTRACT: The computational complexity of the simplex method, widely used for linear programming, depends on the combinatorial diameter of the edge graph of a polyhedron with n facets and dimension d. Despite its popularity, little is known about the (combinatorial) diameter of polytopes, and even for simpler types of complexes. For the case of polytopes, it was conjectured by Hirsch (1957) that the diameter is smaller than (n - d), but this was disproved by Francisco Santos (2010). In this thesis, we present two main results. First, a lower bound on the maximum diameter for two classes of simplicial complexes: pure simplicial complexes and pseudo-manifolds. Second, a topological improvement of Santos’ counter example to the Hirsch Conjecture. This one is (slightly) smaller than the previously known smallest simplicial non-Hirsch sphere.

RESUMEN: La complejidad computacional del método del símplex, ampliamente usado en programación lineal, depende del diámetro combinatorio del grafo de aristas de un poliedro con facetas y dimensión d. Pese a su popularidad, sabemos muy poco sobre el diámetro (combinatorio) de los politopos, incluso para clases más simples de complejos. Para el caso de los politopos, Hirsch (1957) conjeturó que el diámetro era menor que n - d, pero su conjetura fue refutada por Francisco Santos (2010). En esta memoria, presentamos dos resultados fundamentales. Primero, una cota inferior para el diámetro de dos clases de complejos simpliciales: complejos simpliciales puros y pseudo-variedades. Segundo, una mejora topológica del contraejemplo de Santos a la conjetura de Hirsch. Ésta es más pequeña que la anterior esfera simplical no Hirsch más pequeña que se conocía.