Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Francisco Santos ()

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2013, vol. 21, issue 3, 426-460

Abstract: The Hirsch Conjecture, posed in 1957, stated that the graph of a d-dimensional polytope or polyhedron with n facets cannot have diameter greater than n−d. The conjecture itself has been disproved, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the conjecture by more than 25 % is known. This paper reviews several recent attempts and progress on the question. Some work is in the world of polyhedra or (more often) bounded polytopes, but some try to shed light on the question by generalizing it to simplicial complexes. In particular, we include here our recent and previously unpublished proof that the maximum diameter of arbitrary simplicial complexes is in n Θ(d) , and we summarize the main ideas in the polymath 3 project, a web-based collective effort trying to prove an upper bound of type nd for the diameters of polyhedra and of more general objects (including, e.g., simplicial manifolds). Copyright Sociedad de Estadística e Investigación Operativa 2013

Keywords: Polyhedra; diameter; Hirsch Conjecture; Simplex method; Simplicial complex; 52B05; 90C60; 90C05 (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s11750-013-0295-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:21:y:2013:i:3:p:426-460

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-013-0295-7

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().