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

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

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

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

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

Історія

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

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

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

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

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

Примітки

1. Santos, (2011).
2. Kalai, (2010).
3. Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch, Gaussianos, 24 травня 2010, архів оригіналу за 3 березня 2016, процитовано 14 листопада 2020
4. Santos, (2011)
5. Ziegler, (1994), p. 84.
6. Klee та Walkup, (1967).

Література

• 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. Архів оригіналу за 28 жовтня 2019. Процитовано 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, arXiv:math/9204233, doi:10.1090/S0273-0979-1992-00285-9, MR 1130448.
• Klee, Victor; Walkup, David W. (1967), The d-step conjecture for polyhedra of dimension d < 6, Acta Mathematica, 133: 53—78, doi:10.1007/BF02395040, MR 0206823.
• Miranda, Eva (2012), The Hirsch conjecture has been disproved: An interview with Francisco Santos (PDF), Newsletter of the European Mathematical Society (86): 31—36, архів оригіналу (PDF) за 20 березня 2014, процитовано 14 листопада 2020.
• Naddef, Denis (1989), The Hirsch conjecture is true for (0,1)-polytopes, Mathematical Programming, 45 (1): 109—110, doi:10.1007/BF01589099, MR 1017214.
• Santos, Francisco (2011), A counterexample to the Hirsch conjecture, Annals of Mathematics, Princeton University and Institute for Advanced Study, 176 (1): 383—412, arXiv:1006.2814, doi:10.4007/annals.2012.176.1.7, MR 2925387
• Ziegler, Günter M. (1994), The Hirsch Conjecture, Lectures on Polytopes, Graduate Texts in Mathematics, т. 152, Springer-Verlag, с. 83—93.