Гіпотеза Гірша

Для ${\displaystyle d}$-вимірного опуклого багатогранника з ${\displaystyle n}$ гранями, граф, утворений його ребрами і вершинами, має діаметр не більше ${\displaystyle n-d}$.

Тобто будь-які дві вершини багатогранника можна з'єднати один з одним по ланцюжку з не більше ніж ${\displaystyle n-d}$ ребер.

Гіпотезу сформулював Воррен Гірш у листі до Джорджа Данціга в 1957 році. Поштовхом до цього став аналіз симплекс-методу в лінійному програмуванні.

Гірш довів гіпотезу для розмірності 3, а також у кількох часткових випадках. Відомо, що верхня оцінка субекспоненціальна за ${\displaystyle n}$ і ${\displaystyle d}$.

В травні 2010 року Сантос Леал з університету Кантабрії[1][2][3] продемонстрував контрприклад — 43-вимірний багатогранник з 86 гранями і діаметром графу, що перевищує 43. Результат представлено на конференції 100 років у Сіетлі: математики Клі та Ґрюнбаум і з'явився в Анналах математики[4]. Контрприклад не має прямих наслідків для аналізу симплекс-методу, оскільки не виключає можливості більшої, але все ж лінійної чи поліноміальної кількості кроків.

Існують різні еквівалентні формулювання задачі, такі як гіпотеза про d-степінь, яка стверджує, що діаметр будь-якого 2d-фасетового багатогранника в d-вимірному евклідовому просторі не більший від d; контрприклад Леала також спростовує цю гіпотезу[5][6].

Питання про існування лінійної або поліноміальної оцінки залишається відкритим.

• Dantzig, George B. (1963). Linear Programming and Extensions. Princeton Univ. Press.. Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
• Kalai, Gil (10 травня 2010). Francisco Santos Disproves the Hirsch Conjecture. Процитовано 11 травня 2010.
• Kalai, Gil; Kleitman, Daniel J. (1992). A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin of the American Mathematical Society 26 (2): 315–316. MR 1130448. arXiv:math/9204233. doi:10.1090/S0273-0979-1992-00285-9..
• Klee, Victor; Walkup, David W. (1967). The d-step conjecture for polyhedra of dimension d < 6. Acta Mathematica 133: 53–78. MR 0206823. doi:10.1007/BF02395040..
• Miranda, Eva (2012). The Hirsch conjecture has been disproved: An interview with Francisco Santos. Newsletter of the European Mathematical Society (86): 31–36..
• Naddef, Denis (1989). The Hirsch conjecture is true for (0,1)-polytopes. Mathematical Programming 45 (1): 109–110. MR 1017214. doi:10.1007/BF01589099..
• Santos, Francisco (2011). A counterexample to the Hirsch conjecture. Annals of Mathematics (Princeton University and Institute for Advanced Study) 176 (1): 383–412. MR 2925387. arXiv:1006.2814. doi:10.4007/annals.2012.176.1.7.
• Ziegler, Günter M. (1994). The Hirsch Conjecture. Lectures on Polytopes. Graduate Texts in Mathematics 152. Springer-Verlag. с. 83–93..