The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Hirsch Conjecture and its relatives (part I of III)

Francisco Santos

http://personales.unican.es/santosf

Departamento de Matemáticas, Estadística y Computación Universidad de Cantabria, Spain

SLC’70, Ellwangen — March 25–27, 2013

1

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

OR

2

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Hirsch Wars Trilogy

Slides (Seville version, March 2012):

http://personales.unican.es/santosf/Hirsch/Wars

1 Episode I: The Phantom Conjecture. (Today)

2 Episode II: Attack of the Prismatoids + Episode III:

Revenge of the Linear Bound. (Tomorrow)

3 Episode IV: A New Hope. (The day after)

3

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Hirsch Wars Trilogy

Slides (Seville version, March 2012):

http://personales.unican.es/santosf/Hirsch/Wars

1 Episode I: The Phantom Conjecture. (Today)

2 Episode II: Attack of the Prismatoids + Episode III:

Revenge of the Linear Bound. (Tomorrow)

3 Episode IV: A New Hope. (The day after)

3

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Hirsch Wars Trilogy

Slides (Seville version, March 2012):

http://personales.unican.es/santosf/Hirsch/Wars

1 Episode I: The Phantom Conjecture. (Today)

2 Episode II: Attack of the Prismatoids + Episode III:

Revenge of the Linear Bound. (Tomorrow)

3 Episode IV: A New Hope. (The day after)

3

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Hirsch Wars Trilogy

Slides (Seville version, March 2012):

http://personales.unican.es/santosf/Hirsch/Wars

1 Episode I: The Phantom Conjecture. (Today)

2 Episode II: Attack of the Prismatoids + Episode III:

Revenge of the Linear Bound. (Tomorrow)

3 Episode IV: A New Hope. (The day after)

3

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polyhedra and polytopes

ThedimensionofPis the dimension of its affine hull.

4

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polyhedra and polytopes

Definition

A (convex)polyhedronPis the intersection of a finite family of
affine half-spaces inR^{d}.

ThedimensionofPis the dimension of its affine hull.

4

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polyhedra and polytopes

Definition

A (convex)polytopeP is the convex hull of a finite set of points
inR^{d}.

ThedimensionofPis the dimension of its affine hull.

4

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polyhedra and polytopes

Polytope = bounded polyhedron.

Every polytope is a polyhedron, every bounded polyhedron is a polytope.

ThedimensionofPis the dimension of its affine hull.

4

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polyhedra and polytopes

Polytope = bounded polyhedron.

Every polytope is a polyhedron, every bounded polyhedron is a polytope.

ThedimensionofPis the dimension of its affine hull.

4

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Faces of P

LetP be a polytope (or polyhedron) and letHbe a hyperplane not cutting,buttouchingP.

5

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Faces of P

LetP be a polytope (or polyhedron) and letHbe a hyperplane not cutting, buttouchingP.

5

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Faces of P

We say thatH∩Pis afaceofP.

5

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Faces of P

Faces of dimension 0 are calledvertices.

5

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Faces of P

Faces of dimension 1 are callededges.

5

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Faces of P

Faces of dimensiond−1 are calledfacets.

5

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The graph of a polytope

Vertices and edges of a polytopePform a graph (finite, undirected)

The distance d(u,v) between vertices u and v is the length (number of edges) of the shortest path fromu tov.

For example,d(u,v) =2.

6

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The graph of a polytope

Vertices and edges of a polytopePform a graph (finite, undirected)

The distance d(u,v) between vertices u and v is the length (number of edges) of the shortest path fromu tov.

For example,d(u,v) =2.

6

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The graph of a polytope

Vertices and edges of a polytopePform a graph (finite, undirected)

The distance d(u,v) between vertices u and v is the length (number of edges) of the shortest path fromu tov.

For example,d(u,v) =2.

6

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The graph of a polytope

Vertices and edges of a polytopePform a graph (finite, undirected)

ThediameterofG(P)(or ofP) is the maximum distance among its vertices:

diam(P) =max{d(u,v) :u,v ∈V}.

6

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Hirsch conjecture

Conjecture: Warren M. Hirsch (1957)

For every polytopePwithnfacets and dimensiond, diam(P)≤n−d.

polytope facets dimension n−d diameter

cube 6 3 3 3

dodecahedron 12 3 9 5

octahedron 8 3 5 2

k-prism k +2 3 k −1 bk/2c+1

n-cube 2n n n n

7

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Hirsch conjecture

Conjecture: Warren M. Hirsch (1957)

For every polytopePwithnfacets and dimensiond, diam(P)≤n−d.

polytope facets dimension n−d diameter

cube 6 3 3 3

dodecahedron 12 3 9 5

octahedron 8 3 5 2

k-prism k +2 3 k −1 bk/2c+1

n-cube 2n n n n

7

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

1 It was communicated by W. M. Hirsch to G. Dantzig in 1957 (Dantzig had recently invented thesimplex method for linear programming).

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

5 In 2010 I disproved theboundedcase. But the construction does not produce polytopes whose diameter is more than a constant times the Hirsch bound.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

1 It was communicated by W. M. Hirsch to G. Dantzig in 1957 (Dantzig had recently invented thesimplex method for linear programming).

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

5 In 2010 I disproved theboundedcase. But the construction does not produce polytopes whose diameter is more than a constant times the Hirsch bound.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

1 It was communicated by W. M. Hirsch to G. Dantzig in 1957 (Dantzig had recently invented thesimplex method for linear programming).

2 Several special cases have been proved:d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

5 In 2010 I disproved theboundedcase. But the construction does not produce polytopes whose diameter is more than a constant times the Hirsch bound.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

5 In 2010 I disproved theboundedcase.But the construction does not produce polytopes whose diameter is more than a constant times the Hirsch bound.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Brief history of the conjecture

2 Several special cases have been proved: d ≤3,n−d ≤6, 0/1-polytopes, . . .

3 But in the general case**we do not even know of a**
**polynomialbound**for diam(P)in terms ofnandd.

4 In 1967, Klee and Walkup disproved theunboundedcase.

8

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Linear programming

Alinear programis the problem of maximization (or

minimization) of a linear functional subject to linear inequality constraints. That is:

Given

a systemMx ≤b of linear inequalities (b∈R^{n},M ∈R^{d×n}),
and

an objective functionc^{t} ∈R^{d}
Find

max{c^{t} ·x :x ∈R^{d},Mx ≤b}(and a pointx where the
maximum is attained).

9

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Linear programming

Alinear programis the problem of maximization (or

minimization) of a linear functional subject to linear inequality constraints.That is:

Given

a systemMx ≤b of linear inequalities (b∈R^{n},M ∈R^{d×n}),
and

an objective functionc^{t} ∈R^{d}
Find

max{c^{t} ·x :x ∈R^{d},Mx ≤b}(and a pointx where the
maximum is attained).

9

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Linear programming

Alinear programis the problem of maximization (or

minimization) of a linear functional subject to linear inequality constraints. That is:

Given

a systemMx ≤b of linear inequalities (b∈R^{n},M ∈R^{d×n}),
and

an objective functionc^{t} ∈R^{d}
Find

max{c^{t} ·x :x ∈R^{d},Mx ≤b}(and a pointx where the
maximum is attained).

9

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Linear programming

Alinear programis the problem of maximization (or

minimization) of a linear functional subject to linear inequality constraints. That is:

Given

a systemMx ≤b of linear inequalities (b∈R^{n},M ∈R^{d×n}),
and

an objective functionc^{t} ∈R^{d}
Find

max{c^{t} ·x :x ∈R^{d},Mx ≤b}(and a pointx where the
maximum is attained).

9

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Linear programming

Alinear programis the problem of maximization (or

minimization) of a linear functional subject to linear inequality constraints. That is:

Given

a systemMx ≤b of linear inequalities (b∈R^{n},M ∈R^{d×n}),
and

an objective functionc^{t} ∈R^{d}
Find

max{c^{t} ·x :x ∈R^{d},Mx ≤b}(and a pointx where the
maximum is attained).

9

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Linear programming

Alinear programis the problem of maximization (or

minimization) of a linear functional subject to linear inequality constraints. That is:

Given

a systemMx ≤b of linear inequalities (b∈R^{n},M ∈R^{d×n}),
and

an objective functionc^{t} ∈R^{d}
Find

max{c^{t} ·x :x ∈R^{d},Mx ≤b}(and a pointx where the
maximum is attained).

9

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Linear programming

Alinear programis the problem of maximization (or

minimization) of a linear functional subject to linear inequality constraints. That is:

Given

a systemMx ≤b of linear inequalities (b∈R^{n},M ∈R^{d×n}),
and

an objective functionc^{t} ∈R^{d}
Find

max{c^{t} ·x :x ∈R^{d},Mx ≤b}(and a pointx where the
maximum is attained).

9

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## A brief history of linear programming

It was invented in the 1940’s by G. Dantzig, L. Kantorovich and J. von Neumann.

In particular, in 1947 G. Dantzig devised thesimplex method: The first practical algorithm for solving linear programs (and still the one most used).

Around 1980 twopolynomial timealgorithms for linear programming were proposed by Khachiyan and Karmakar (ellipsoidandinterior pointmethod).

None of these algorithms isstrongly polynomial. Finding strongly polynomial algorithms for linear programmingis one of the “mathematical problems for the 21st century"

proposed by S. Smale in 2000.

10

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## A brief history of linear programming

It was invented in the 1940’s by G. Dantzig, L. Kantorovich and J. von Neumann.

In particular, in 1947 G. Dantzig devised thesimplex method: The first practical algorithm for solving linear programs (and still the one most used).

Around 1980 twopolynomial timealgorithms for linear programming were proposed by Khachiyan and Karmakar (ellipsoidandinterior pointmethod).

None of these algorithms isstrongly polynomial. Finding strongly polynomial algorithms for linear programmingis one of the “mathematical problems for the 21st century"

proposed by S. Smale in 2000.

10

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## A brief history of linear programming

It was invented in the 1940’s by G. Dantzig, L. Kantorovich and J. von Neumann.

In particular, in 1947 G. Dantzig devised thesimplex method: The first practical algorithm for solving linear programs (and still the one most used).

Around 1980 twopolynomial timealgorithms for linear programming were proposed by Khachiyan and Karmakar (ellipsoidandinterior pointmethod).

None of these algorithms isstrongly polynomial. Finding strongly polynomial algorithms for linear programmingis one of the “mathematical problems for the 21st century"

proposed by S. Smale in 2000.

10

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## A brief history of linear programming

It was invented in the 1940’s by G. Dantzig, L. Kantorovich and J. von Neumann.

proposed by S. Smale in 2000.

10

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## A brief history of linear programming

It was invented in the 1940’s by G. Dantzig, L. Kantorovich and J. von Neumann.

proposed by S. Smale in 2000.

10

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## A brief history of linear programming

It was invented in the 1940’s by G. Dantzig, L. Kantorovich and J. von Neumann.

proposed by S. Smale in 2000.

10

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Connection to the Hirsch conjecture

The set of feasible solutionsP={x ∈R^{d} :Mx≤b}is a
polyhedronPwith (at most)nfacets andd dimensions.

The optimal solution (if it exists) is always attained at a vertex.

Thesimplex method[Dantzig 1947] solves the linear program by starting at any feasible vertex and moving along the graph ofP, in a monotone fashion, until the optimum is attained.

In particular, (the polynomial version of) the Hirsch

conjecture is related to the question of whether the simplex method is a polynomial-time algorithm. A polynomialpivot rulefor the simplex method would answer Smale’s

question in the affirmative.

11

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Connection to the Hirsch conjecture

The set of feasible solutionsP={x ∈R^{d} :Mx≤b}is a
polyhedronPwith (at most)nfacets andd dimensions.

The optimal solution (if it exists) is always attained at a vertex.

Thesimplex method[Dantzig 1947] solves the linear program by starting at any feasible vertex and moving along the graph ofP, in a monotone fashion, until the optimum is attained.

In particular, (the polynomial version of) the Hirsch

conjecture is related to the question of whether the simplex method is a polynomial-time algorithm. A polynomialpivot rulefor the simplex method would answer Smale’s

question in the affirmative.

11

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Connection to the Hirsch conjecture

The set of feasible solutionsP={x ∈R^{d} :Mx≤b}is a
polyhedronPwith (at most)nfacets andd dimensions.

The optimal solution (if it exists) is always attained at a vertex.

Thesimplex method[Dantzig 1947] solves the linear program by starting at any feasible vertex and moving along the graph ofP, in a monotone fashion, until the optimum is attained.

In particular, (the polynomial version of) the Hirsch

conjecture is related to the question of whether the simplex method is a polynomial-time algorithm. A polynomialpivot rulefor the simplex method would answer Smale’s

question in the affirmative.

11

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Connection to the Hirsch conjecture

^{d} :Mx≤b}is a
polyhedronPwith (at most)nfacets andd dimensions.

The optimal solution (if it exists) is always attained at a vertex.

In particular, (the polynomial version of) the Hirsch

question in the affirmative.

11

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Connection to the Hirsch conjecture

^{d} :Mx≤b}is a
polyhedronPwith (at most)nfacets andd dimensions.

The optimal solution (if it exists) is always attained at a vertex.

In particular, (the polynomial version of) the Hirsch

question in the affirmative.

11

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Connection to the Hirsch conjecture

^{d} :Mx≤b}is a
polyhedronPwith (at most)nfacets andd dimensions.

The optimal solution (if it exists) is always attained at a vertex.

In particular, (the polynomial version of) the Hirsch

question in the affirmative.

11

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polynomial Hirsch conjecture

In this sense, more important than the standard Hirsch

conjecture (which is false) is the following “polynomial version”

of it:

Polynomial Hirsch Conjecture

LetH(n,d)denote the maximum diameter ofd-polyhedra with nfacets. There is a constantk such that:

H(n,d)≤n^{k}, ∀n,d.

12

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polynomial Hirsch conjecture

In this sense, more important than the standard Hirsch

conjecture (which is false) is the following “polynomial version”

of it:

Polynomial Hirsch Conjecture

LetH(n,d)denote the maximum diameter ofd-polyhedra with nfacets. There is a constantk such that:

H(n,d)≤n^{k}, ∀n,d.

12

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polynomial Hirsch conjecture

In this sense, more important than the standard Hirsch

conjecture (which is false) is the following “polynomial version”

of it:

Polynomial Hirsch Conjecture

LetH(n,d)denote the maximum diameter ofd-polyhedra with nfacets. There is a constantk such that:

H(n,d)≤n^{k}, ∀n,d.

12

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “As simple as possible”

Definition

Ad-polytope/polyhedron issimpleif at every vertex exactlyd facets meet. ('facet-defining hyperplanes are “in general position”).

Ad-polytope issimplicialif every facet has exactlyd vertices.

That is, if every proper face is a simplex. ('vertices are “in general position”).

Of course, the (polar) dual of a simple polytope is simplicial, and vice-versa.

Lemma (Klee 1964)

For every n and d the maximum diameter of d -polytopes / d -polyhedra with n facets is achieved at a simple one.

13

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “As simple as possible”

Definition

Ad-polytope/polyhedron issimpleif at every vertex exactlyd facets meet. ('facet-defining hyperplanes are “in general position”).

Ad-polytope issimplicialif every facet has exactlyd vertices.

That is, if every proper face is a simplex. ('vertices are “in general position”).

Of course, the (polar) dual of a simple polytope is simplicial, and vice-versa.

Lemma (Klee 1964)

For every n and d the maximum diameter of d -polytopes / d -polyhedra with n facets is achieved at a simple one.

13

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “As simple as possible”

Definition

Ad-polytope/polyhedron issimpleif at every vertex exactlyd facets meet. ('facet-defining hyperplanes are “in general position”).

Ad-polytope issimplicialif every facet has exactlyd vertices.

That is, if every proper face is a simplex. ('vertices are “in general position”).

Of course, the (polar) dual of a simple polytope is simplicial, and vice-versa.

Lemma (Klee 1964)

For every n and d the maximum diameter of d -polytopes / d -polyhedra with n facets is achieved at a simple one.

13

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “As simple as possible”

Definition

Ad-polytope issimplicialif every facet has exactlyd vertices.

That is, if every proper face is a simplex. ('vertices are “in general position”).

Of course, the (polar) dual of a simple polytope is simplicial, and vice-versa.

Lemma (Klee 1964)

13

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “As simple as possible”

Remark

We will often dualize the problem. We want to travel from one facet to another of a polytopeQ(the polar ofP) along the “dual graph”, whose edges correspond toridgesofQ.

By the Klee lemma we can restrict our attention to simplicial polytopes; their face lattices aresimplicial complexeswith the topology of a(d−1)-sphere. (Simplicial(d−1)-spheres).

14

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “As simple as possible”

Remark

We will often dualize the problem. We want to travel from one facet to another of a polytopeQ(the polar ofP) along the “dual graph”, whose edges correspond toridgesofQ.

By the Klee lemma we can restrict our attention to simplicial polytopes; their face lattices aresimplicial complexeswith the topology of a(d−1)-sphere. (Simplicial(d−1)-spheres).

14

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “. . . but not simpler”

Q: What is the polar of a (simple) unbounded polyhedron?

15

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “. . . but not simpler”

Q: What is the polar of a (simple) unbounded polyhedron?

A: It must be a simplicial complex with the topology of a ball and with some “convexity constraint”

15

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## “. . . but not simpler”

Q: What is the polar of a (simple) unbounded polyhedron?

A: It must be a simplicial complex with the topology of a ball and with some “convexity constraint”

The polar of an unboundedd-polyhedron withnfacets “is” a
regular triangulation ofnpoints inR^{d−1}.

15

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup non-Hirsch (8,4)-polyhedron

Klee and Walkup proved:

Theorem (Klee-Walkup 1967)

There is a4-dimensional unbounded polyhedron with8facets and diameter5.

Let us prove the following equivalent version:

Theorem

There is a regular triangulation of8points inR^{3}that has two
tetrahedra at distance five from one another.

16

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup non-Hirsch (8,4)-polyhedron

Klee and Walkup proved:

Theorem (Klee-Walkup 1967)

There is a4-dimensional unbounded polyhedron with8facets and diameter5.

Let us prove the following equivalent version:

Theorem

There is a regular triangulation of8points inR^{3}that has two
tetrahedra at distance five from one another.

16

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup non-Hirsch (8,4)-polyhedron

Klee and Walkup proved:

Theorem (Klee-Walkup 1967)

There is a4-dimensional unbounded polyhedron with8facets and diameter5.

Let us prove the following equivalent version:

Theorem

There is a regular triangulation of8points inR^{3}that has two
tetrahedra at distance five from one another.

16

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup non-Hirsch (8,4)-polyhedron

Proof.

This is a(Cayley Trick view of a)3D triangulation with 8 vertices and diameter 4:

*d*

*f*

*e*
*h*
*g*
*b*

*a*

*c*

17

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup non-Hirsch (8,4)-polyhedron

Proof.

This is a(Cayley Trick view of a)3D triangulation with 8 vertices and diameter 4:

*d*

*f*

*e*
*h*
*g*
*b*

*a*

*c*

Three steps are needed to go from any light triangle to any dark triangle.

17

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup non-Hirsch (8,4)-polyhedron

Proof.

This is a(Cayley Trick view of a)3D triangulation with 8 vertices and diameter 4:

*d*

*f*

*e*
*h*
*g*
*b*

*a*

*c*

Gluing two more tetrahedra (one on top, one on bottom), we get diameter 5.

17

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup Hirsch-sharp (9,4)-polytope

The counter-example to theunboundedHirsch conjecture is
**equivalent**to the existence of a 4-polytope with 9 facets and
with diameter 5:

18

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup Hirsch-sharp (9,4)-polytope

The counter-example to theunboundedHirsch conjecture is
**equivalent**to the existence of a 4-polytope with 9 facets and
with diameter 5:

bounded Hirsch-sharp ⇒ unbounded non-Hirsch From a bounded(9,4)-polytopewe get anunbounded

(8,4)-polyhedronwith(at least)the same diameter by projectively sending the “9th facet” to infinity. (9=n>2d =8 is needed)

*F*
*u*

*v*

*u’*

*v’*

π

18

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The Klee-Walkup Hirsch-sharp (9,4)-polytope

The counter-example to theunboundedHirsch conjecture is
**equivalent**to the existence of a 4-polytope with 9 facets and
with diameter 5:

bounded Hirsch-sharp ⇐ unbounded non-Hirsch From an unbounded(8,4)-polyhedronof diameter>4 we get a (9,4)-polytopewith diameter (at least) 5, by considering

“infinity” a new facetF.

*F*

*u* *v*

*u’*

*v’*

π

18

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

Polynomial bound for network flow polytopes [Goldfarb 1992, Orlin 1997], totally unimodular [Dyer-Frieze 1994], problems with bounded minors [Bonifas et al. 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

Polynomial bound for network flow polytopes [Goldfarb 1992, Orlin 1997], totally unimodular [Dyer-Frieze 1994], problems with bounded minors [Bonifas et al. 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

Polynomial bound for network flow polytopes [Goldfarb 1992, Orlin 1997], totally unimodular [Dyer-Frieze 1994], problems with bounded minors [Bonifas et al. 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

Polynomial bound for network flow polytopes [Goldfarb 1992, Orlin 1997],totally unimodular [Dyer-Frieze 1994], problems with bounded minors [Bonifas et al. 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Some known cases

Hirsch conjecture holds for d ≤3: [Klee 1966].

n−d ≤6: [Klee-Walkup, 1967] [Bremner-Schewe, 2008]

H(9,4) =H(10,4) =5 [Klee-Walkup, 1967]

H(11,4) =6 [Schuchert, 1995],

H(12,4) =H(12,5) =7 [Bremner et al. 2012].

0-1 polytopes [Naddef 1989]

Flag polytopes (and flag normal simplicial complexes) [Adiprasito-Benedetti, 2013+]

. . .

19

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polynomial bounds, under perturbation

Given a linear program withd variables andnrestrictions, we consider a random perturbation of the matrix, within a

parameter(normal distribution).

Theorem [Spielman-Teng 2004] [Vershynin 2006]

The expected running time of the simplex method(with the
shadow boundary pivot rule)on the perturbed polyhedron is
polynomial ind and^{−1}, and polylogarithmic inn.

20

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Polynomial bounds, under perturbation

Given a linear program withd variables andnrestrictions, we consider a random perturbation of the matrix, within a

parameter(normal distribution).

Theorem [Spielman-Teng 2004] [Vershynin 2006]

The expected running time of the simplex method(with the
shadow boundary pivot rule)on the perturbed polyhedron is
polynomial ind and^{−1}, and polylogarithmic inn.

20

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The two best general bounds

LetH(n,d) :=max. diameter of ad-polyhedron withnfacets.

Theorem [Kalai-Kleitman 1992], “quasi-polynomial”

H(n,d)≤n^{log}^{2}^{d+2}, ∀n,d.

Theorem [Barnette 1967, Larman 1970], “linear in fixedd”
H(n,d)≤n2^{d−3}, ∀n,d.

The proofs of both aresurprisingly simpleand valid for the dual graph of everynormal, puresimplicial complex.

21

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The two best general bounds

LetH(n,d) :=max. diameter of ad-polyhedron withnfacets.

Theorem [Kalai-Kleitman 1992], “quasi-polynomial”

H(n,d)≤n^{log}^{2}^{d+2}, ∀n,d.

Theorem [Barnette 1967, Larman 1970], “linear in fixedd”
H(n,d)≤n2^{d−3}, ∀n,d.

The proofs of both aresurprisingly simpleand valid for the dual graph of everynormal, puresimplicial complex.

21

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The two best general bounds

LetH(n,d) :=max. diameter of ad-polyhedron withnfacets.

Theorem [Kalai-Kleitman 1992], “quasi-polynomial”

H(n,d)≤n^{log}^{2}^{d+2}, ∀n,d.

Theorem [Barnette 1967, Larman 1970], “linear in fixedd”
H(n,d)≤n2^{d−3}, ∀n,d.

The proofs of both aresurprisingly simpleand valid for the dual graph of everynormal, puresimplicial complex.

21

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## The two best general bounds

LetH(n,d) :=max. diameter of ad-polyhedron withnfacets.

Theorem [Kalai-Kleitman 1992], “quasi-polynomial”

H(n,d)≤n^{log}^{2}^{d+2}, ∀n,d.

Theorem [Barnette 1967, Larman 1970], “linear in fixedd”
H(n,d)≤n2^{d−3}, ∀n,d.

21

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Normal simplicial complexes

Definition

A pure simplicial complex is callednormalif the dual graph of everylinkis connected. (That is, if every link isstrongly connected)

The Kalai-Kleitman bound follows from the following recursion

(where, now,H(n,d)denotes the max. diameter among normal and pure simplicial(d−1)-complexes withnvertices):

H(n,d)≤2H(bn/2c,d) +H(n−1,d −1) +2.

22

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## Normal simplicial complexes

Definition

A pure simplicial complex is callednormalif the dual graph of everylinkis connected. (That is, if every link isstrongly connected)

The Kalai-Kleitman bound follows from the following recursion

(where, now,H(n,d)denotes the max. diameter among normal and pure simplicial(d−1)-complexes withnvertices):

H(n,d)≤2H(bn/2c,d) +H(n−1,d −1) +2.

22

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## H(n, d ) ≤ 2H(bn/2c, d ) + H(n − 1, d − 1) + 2.

Proof.

Letu,v be two simplices in a normal, pure simplic. complexK.
For eachi∈N, letU_{i} be thei-neighborhood ofu(the
subcomplex consisting of all simplices at distance at mostifromu).

LetV_{j} thej-neighborhood ofv.

Leti_{0}(resp.j0)be the smallest value such thatU_{i}_{0} (resp.Vj_{0})

contains more than half of the vertices. This impliesi_{0}−1
andj_{0}−1 are at mostH(bn/2c,d).

Letu^{0} ∈U_{i}_{0} andv^{0} ∈V_{j}_{0} having a common vertex. Then:

dist(u^{0},v^{0})≤H(n−1,d−1).

So: d(u,v)≤dist(u,u^{0}) +dist(u^{0},v^{0}) +dist(v^{0},v)≤

≤2H(bn/2c,d) +H(n−1,d −1) +2.

23

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## H(n, d ) ≤ 2H(bn/2c, d ) + H(n − 1, d − 1) + 2.

Proof.

Letu,v be two simplices in a normal, pure simplic. complexK.
For eachi∈N, letU_{i} be thei-neighborhood ofu(the
subcomplex consisting of all simplices at distance at mostifromu).

LetV_{j} thej-neighborhood ofv.

Leti_{0}(resp.j0)be the smallest value such thatU_{i}_{0} (resp.Vj_{0})

contains more than half of the vertices. This impliesi_{0}−1
andj_{0}−1 are at mostH(bn/2c,d).

Letu^{0} ∈U_{i}_{0} andv^{0} ∈V_{j}_{0} having a common vertex. Then:

dist(u^{0},v^{0})≤H(n−1,d−1).

So: d(u,v)≤dist(u,u^{0}) +dist(u^{0},v^{0}) +dist(v^{0},v)≤

≤2H(bn/2c,d) +H(n−1,d −1) +2.

23

The Hirsch Conjecture Motivation: LP 1967: A 1st counter-example Cases and bounds Thed-step Theorem

## H(n, d ) ≤ 2H(bn/2c, d ) + H(n − 1, d − 1) + 2.

Proof.

Letu,v be two simplices in a normal, pure simplic. complexK.
For eachi∈N, letU_{i} be thei-neighborhood ofu(the
subcomplex consisting of all simplices at distance at mostifromu).

LetV_{j} thej-neighborhood ofv.

Leti_{0}(resp.j0)be the smallest value such thatU_{i}_{0} (resp.Vj_{0})

contains more than half of the vertices. This impliesi_{0}−1
andj_{0}−1 are at mostH(bn/2c,d).

Letu^{0} ∈U_{i}_{0} andv^{0} ∈V_{j}_{0} having a common vertex. Then:

dist(u^{0},v^{0})≤H(n−1,d−1).

So: d(u,v)≤dist(u,u^{0}) +dist(u^{0},v^{0}) +dist(v^{0},v)≤

≤2H(bn/2c,d) +H(n−1,d −1) +2.

23