Гіпотеза Гірша
Гіпотеза Гірша — спростована гіпотеза про діаметр графу багатогранника.
Для -вимірного опуклого багатогранника з гранями, граф, утворений його ребрами і вершинами, має діаметр не більше .
Тобто будь-які дві вершини багатогранника можна з'єднати один з одним по ланцюжку з не більше ніж ребер.
Гіпотезу сформулював Воррен Гірш[de] у листі до Джорджа Данціга в 1957 році. Поштовхом до цього став аналіз симплекс-методу в лінійному програмуванні.
Гірш довів гіпотезу для розмірності 3, а також у кількох часткових випадках. Відомо, що верхня оцінка субекспоненціальна за і .
В травні 2010 року Сантос Леал[ru] з університету Кантабрії[en][1][2][3] продемонстрував контрприклад — 43-вимірний багатогранник з 86 гранями і діаметром графу, що перевищує 43. Результат представлено на конференції 100 років у Сіетлі: математики Клі[en] та Ґрюнбаум і з'явився в Анналах математики[4]. Контрприклад не має прямих наслідків для аналізу симплекс-методу, оскільки не виключає можливості більшої, але все ж лінійної чи поліноміальної кількості кроків.
Існують різні еквівалентні формулювання задачі, такі як гіпотеза про d-степінь, яка стверджує, що діаметр будь-якого 2d-фасетового багатогранника в d-вимірному евклідовому просторі не більший від d; контрприклад Леала також спростовує цю гіпотезу[5][6].
Питання про існування лінійної або поліноміальної оцінки залишається відкритим.
- ↑ Santos, (2011).
- ↑ Kalai, (2010).
- ↑ Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch, Gaussianos, 24 травня 2010, архів оригіналу за 3 березня 2016, процитовано 14 листопада 2020
- ↑ Santos, (2011)
- ↑ Ziegler, (1994), p. 84.
- ↑ 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.