Geodesic
A counterexample to the Hirsch Conjecture
Francisco Santos1
1 Departamento de Matemáticas, Universidad de Cantabria, Av. de los Castros 48, E-39005 Santander, Spain
Annals of mathematics, Tome 176 (2012) no. 1, pp. 383-412

Voir la notice de l'article provenant de la source Annals of Mathematics website

The Hirsch Conjecture (1957) stated that the graph of a $d$-dimensional polytope with $n$ facets cannot have (combinatorial) diameter greater than $n-d$. That is, any two vertices of the polytope can be connected by a path of at most $n-d$ edges.
This paper presents the first counterexample to the conjecture. Our polytope has dimension $43$ and $86$ facets. It is obtained from a $5$-dimensional polytope with $48$ facets that violates a certain generalization of the $d$-step conjecture of Klee and Walkup.

DOI : 10.4007/annals.2012.176.1.7

Francisco Santos 1

1 Departamento de Matemáticas, Universidad de Cantabria, Av. de los Castros 48, E-39005 Santander, Spain 
@article{10_4007_annals_2012_176_1_7,
     author = {Francisco Santos},
     title = {A counterexample to the {Hirsch} {Conjecture}},
     journal = {Annals of mathematics},
     pages = {383--412},
     publisher = {mathdoc},
     volume = {176},
     number = {1},
     year = {2012},
     doi = {10.4007/annals.2012.176.1.7},
     mrnumber = {2925387},
     zbl = {1252.52007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.7/}
}
TY  - JOUR
AU  - Francisco Santos
TI  - A counterexample to the Hirsch Conjecture
JO  - Annals of mathematics
PY  - 2012
SP  - 383
EP  - 412
VL  - 176
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.7/
DO  - 10.4007/annals.2012.176.1.7
LA  - en
ID  - 10_4007_annals_2012_176_1_7
ER  - 
%0 Journal Article
%A Francisco Santos
%T A counterexample to the Hirsch Conjecture
%J Annals of mathematics
%D 2012
%P 383-412
%V 176
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.7/
%R 10.4007/annals.2012.176.1.7
%G en
%F 10_4007_annals_2012_176_1_7
Francisco Santos. A counterexample to the Hirsch Conjecture. Annals of mathematics, Tome 176 (2012) no. 1, pp. 383-412. doi: 10.4007/annals.2012.176.1.7

Cité par Sources :