다항 허시 추측 — 다포체의 지름은 다항식인가

$d$차원 유계 볼록 다포체가 *$n$개 면(facet)을 가질 때, 그래프 지름(한 꼭짓점에서 다른 꼭짓점까지의 최단 모서리 경로 길이)이 $n, d$의 다항식*으로 유계인가?

Klee–Walkup 1967. 강한 형태 *$\le n - d$ (Hirsch 1957)는 Santos 2010에서 반증*됨.

최악 케이스 지름 $\Delta(d,n)$의 성장률은 50년 넘게 미해결이다. Klee–Minty 1972 cube는 다포체 그래프의 지름이 작아도 특정 simplex pivot 규칙은 $2^d$ 단계를 밟을 수 있음을 보여준다. 따라서 다항 지름이 증명되면 임의의 두 꼭짓점 사이에 짧은 모서리 경로가 존재한다는 강한 구조 정리가 되지만, 그 경로를 효율적으로 찾는 pivot 규칙이나 새로운 다항 시간 알고리즘이 자동으로 따라오지는 않는다.

Santos 2010-12-08 (arXiv) — 43차원 86-facet 다포체가 *Hirsch 추측 $86-43=43$을 초과하는 지름 44 발견 → 강한 Hirsch 반증. Kalai–Kleitman 1992*: $\Delta(d, n) \le n^{1 + \log_2 d}$ — 50년 가장 좋은 상한. Todd 2014가 $\Delta(d, n) \le (n-d)^{\log_2 d}$로 미세 개선.