FranciscoSantoshttp://personales.unican.es/santosf TheHirschConjectureanditsrelatives(partIofIII)

(1)

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

(2)

OR

2

(3)

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

(4)

Hirsch Wars Trilogy

3

(5)

Hirsch Wars Trilogy

3

(6)

Hirsch Wars Trilogy

3

(7)

Polyhedra and polytopes

ThedimensionofPis the dimension of its affine hull.

4

(8)

Polyhedra and polytopes

Definition

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

4

(9)

Polyhedra and polytopes

Definition

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

4

(10)

Polyhedra and polytopes

Polytope = bounded polyhedron.

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

4

(11)

Polyhedra and polytopes

Polytope = bounded polyhedron.

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

4

(12)

Faces of P

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

5

(13)

Faces of P

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

5

(14)

Faces of P

We say thatH∩Pis afaceofP.

5

(15)

Faces of P

Faces of dimension 0 are calledvertices.

5

(16)

Faces of P

Faces of dimension 1 are callededges.

5

(17)

Faces of P

Faces of dimensiond−1 are calledfacets.

5

(18)

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

(19)

The graph of a polytope

6

(20)

The graph of a polytope

6

(21)

The graph of a polytope

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

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

6

(22)

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

(23)

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

(24)

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 casewe do not even know of a polynomialboundfor 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

(25)

Brief history of the conjecture

8

(26)

Brief history of the conjecture

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

8

(27)

Brief history of the conjecture

8

(28)

Brief history of the conjecture

8

(29)

Brief history of the conjecture

8

(30)

Brief history of the conjecture

8

(31)

Brief history of the conjecture

8

(32)

Brief history of the conjecture

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

(33)

Brief history of the conjecture

8

(34)

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ⁿ,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

(35)

Linear programming

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

Given

9

(36)

Linear programming

Given

9

(37)

Linear programming

Given

9

(38)

Linear programming

Given

9

(39)

Linear programming

Given

9

(40)

Linear programming

Given

9

(41)

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

(42)

A brief history of linear programming

10

(43)

A brief history of linear programming

10

(44)

A brief history of linear programming

10

(45)

A brief history of linear programming

10

(46)

A brief history of linear programming

10

(47)

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

(48)

Connection to the Hirsch conjecture

11

(49)

Connection to the Hirsch conjecture

11

(50)

Connection to the Hirsch conjecture

11

(51)

Connection to the Hirsch conjecture

11

(52)

Connection to the Hirsch conjecture

11

(53)

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

(54)

Polynomial Hirsch conjecture

of it:

12

(55)

Polynomial Hirsch conjecture

of it:

12

(56)

“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

(57)

“As simple as possible”

Definition

Lemma (Klee 1964)

13

(58)

“As simple as possible”

Definition

Lemma (Klee 1964)

13

(59)

“As simple as possible”

Definition

Lemma (Klee 1964)

13

(60)

“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

(61)

“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

(62)

“. . . but not simpler”

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

15

(63)

“. . . but not simpler”

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

15

(64)

“. . . but not simpler”

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

(65)

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³that has two tetrahedra at distance five from one another.

16

(66)

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

Theorem

16

(67)

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

Theorem

16

(68)

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

(69)

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

Proof.

d

f

e h g b

a

c

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

17

(70)

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

Proof.

d

f

e h g b

a

c

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

17

(71)

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

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

18

(72)

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

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

(73)

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

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

(74)

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

(75)

Some known cases

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].

. . .

19

(76)

Some known cases

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].

. . .

19

(77)

Some known cases

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].

. . .

19

(78)

Some known cases

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].

. . .

19

(79)

Some known cases

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].

. . .

19

(80)

Some known cases

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].

. . .

19

(81)

Some known cases

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].

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

. . .

19

(82)

Some known cases

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].

. . .

19

(83)

Some known cases

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].

. . .

19

(84)

Some known cases

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].

. . .

19

(85)

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⁻¹, and polylogarithmic inn.

20

(86)

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⁻¹, and polylogarithmic inn.

20

(87)

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²^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

(88)

The two best general bounds

21

(89)

The two best general bounds

21

(90)

The two best general bounds

21

(91)

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

(92)

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

(93)

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₀(resp.j0)be the smallest value such thatU_i₀ (resp.Vj₀)

contains more than half of the vertices. This impliesi₀−1 andj₀−1 are at mostH(bn/2c,d).

Letu⁰ ∈U_i₀ andv⁰ ∈V_j₀ having a common vertex. Then:

dist(u⁰,v⁰)≤H(n−1,d−1).

So: d(u,v)≤dist(u,u⁰) +dist(u⁰,v⁰) +dist(v⁰,v)≤

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

23

(94)

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

Proof.

dist(u⁰,v⁰)≤H(n−1,d−1).

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

23

(95)

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

Proof.

dist(u⁰,v⁰)≤H(n−1,d−1).

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

23