Гіпотеза Гірша — спростована гіпотеза про діаметр графу багатогранника.
Формулювання Для -вимірного опуклого багатогранника з гранями, граф, утворений його ребрами і вершинами, має діаметр не більше .
Тобто будь-які дві вершини багатогранника можна з'єднати один з одним по ланцюжку з не більше ніж ребер.
Історія
Гіпотезу сформулював у листі до Джорджа Данціга в 1957 році. Поштовхом до цього став аналіз симплекс-методу в лінійному програмуванні.
Гірш довів гіпотезу для розмірності 3, а також у кількох часткових випадках. Відомо, що верхня оцінка субекспоненціальна за і .
В травні 2010 року з .. продемонстрував контрприклад — 43-вимірний багатогранник з 86 гранями і діаметром графу, що перевищує 43. Результат представлено на конференції 100 років у Сіетлі: математики та Ґрюнбаум і з'явився в Анналах математики. Контрприклад не має прямих наслідків для аналізу симплекс-методу, оскільки не виключає можливості більшої, але все ж лінійної чи поліноміальної кількості кроків.
Існують різні еквівалентні формулювання задачі, такі як гіпотеза про d-степінь, яка стверджує, що діаметр будь-якого 2d-фасетового багатогранника в d-вимірному евклідовому просторі не більший від d; контрприклад Леала також спростовує цю гіпотезу, p. 84...
Питання про існування лінійної або поліноміальної оцінки залишається відкритим.
Примітки
Література . Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
. . . .
.