Running time bound
- Each iteration (vertex → vertex) takes polynomial time; the number of iterations is at most the number of vertices (
38:07,38:38). - Crudest bound on vertices:
C(n, m)("n choose m"), since vertices are represented by bases of sizem— exponential (38:38). - Sharper bound: the number of vertices is at most
C((n − m)/2, m/2)(39:02).- Why any improvement is possible: given a basis, the vertex is
A_B⁻¹ b, which may fail to be non-negative and therefore may be infeasible — not every basis yields a vertex (39:37,39:58). - Attribution: this follows from the upper bound theorem of McMullen, per Michel Goemans; it was a major open problem for a long time before McMullen solved it, so it is not an easy fact (
40:13,40:39).
- Why any improvement is possible: given a basis, the vertex is
- Either way the count is still a very big number (
40:39).
The polytope graph and its diameter
- Model the polytope as a graph: nodes = polytope vertices, edges = neighboring vertices (
41:31). Two vertices are adjacent iff their bases differ by a single constraint (51:36). - Necessary condition for a poly-time simplex: every polytope in
ddimensions defined bymhyperplanes has graph diameterpoly(m, d)(42:38). - It is not sufficient — simplex does not necessarily follow the shortest path (
42:02,46:12). - What "an implementation of simplex" means here comes down entirely to the pivoting rule: which negative-reduced-cost
jto increment, and which zero coordinate inBto kick out (42:02,42:21).
The Hirsch conjecture and its fall
| Item | Detail |
|---|---|
| Conjecture (Hirsch, 1957) | Diameter is at most m − d (43:47) |
| Disproof | Santos, Annals of Mathematics, 2011 (44:31) |
| Counterexample | Explicit polytope with d = 43, m = 86, diameter ≥ 44 — off by one (44:31) |
| Stronger follow-up | For fixed d and any ε > 0, an infinite family of polytopes with m → ∞ and diameter ≥ (1 + ε)m (45:12) |