One great problem, three kinds of immersion

From a story to your own conjecture

Problem stories open curiosity. The problem workshop is the next place, where curiosity becomes a testable idea.

1 · DiscoverMeet the questionLearn when it appeared and why it still holds people’s attention.
2 · ChallengeTest one caseMake your first observation in five minutes with a drawing, calculation, or colors.
3 · DevelopYou are hereBuild on ideasPublish an observation and grow it through comparisons, conjectures, and counterexamples.

Week 21 · MathOverflowOpen

Polynomial Hirsch Conjecture — Is Polytope Diameter Polynomial?

Research level· Posed 1957

Problem

For any bounded convex polytope of dimension $d$ with $n$ facets, is its graph diameter bounded by a polynomial in $n$ and $d$ ? The original Hirsch conjecture $\le n - d$ was disproved by Santos (2010); the polynomial version remains open.

Why it matters

The conjecture connects polytope combinatorics with linear programming. Klee–Minty cubes show that a small graph diameter does not prevent a particular simplex pivot rule from taking exponentially many steps. A polynomial diameter would guarantee short edge paths exist, but would not by itself provide an efficient pivot rule or a new polynomial-time algorithm.

Progress so far

Santos (2010) disproved the original Hirsch conjecture with a 43-dimensional 86-facet counterexample. The best known upper bound is $\Delta \le n^{1 + \log_2 d}$ (Kalai-Kleitman 1992). The polynomial form remains wide open.

💡 Explore together, one line at a time(0 contributions)

Contributions are not ranked by popularity. Curator feedback names what is clear or reproducible, and peer signals mean someone understood or actually reproduced it.

What did you notice?

You do not need a complete proof. A small observation can open the next path.

Markdown + KaTeX supported (`$x^2$` inline, `$$\sum_{k=1}^n k$$` display)

0 / 3000 characters

moderation policy. Sign in after submitting if you want to edit or delete this attempt from another device.

Loading…