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

Гіпотеза Гірша — спростована гіпотеза про діаметр графу багатогранника.

Формулювання

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

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

Історія

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

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

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

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

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

Література

• Шаблон:Citation. Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
• Шаблон:Cite web
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation.