Гипотеза Хирша

Гипотеза Хирша — опровергнутая гипотеза о диаметре графа многогранника, предполагала, что для ${\displaystyle d}$-мерного выпуклого многогранника с ${\displaystyle n}$ гранями, граф, образованный его рёбрами и вершинами, имеет диаметр не больше ${\displaystyle n-d}$ (то есть любые две вершины многогранника можно соединить друг с другом по цепочке из не более чем ${\displaystyle n-d}$ рёбер).

Сформулирована в письме Уоррена Хирша^[нем.] Джорджу Данцигу в 1957 году, предположение возникло по результатам анализа симплекс-метода в линейном программировании. Хирш доказал гипотезу в размерности 3, а также в нескольких частных случаях.

Известно, что верхняя оценка субэкспоненциальна по ${\displaystyle n}$ и ${\displaystyle d}$.

В мае 2010 года Франсиско Сантос Леал предъявил контрпример — 43-мерный многогранник с 86 гранями и диаметром графа, превышающим 43. Вопрос о существовании линейной или полиномиальной оценки по состоянию на 2024 год остаётся открытым.

Литература

• 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. Francisco Santos Disproves the Hirsch Conjecture  (неопр.) (10 мая 2010). Дата обращения: 11 мая 2010. Архивировано 28 октября 2019 года.
• 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 Архивная копия от 20 марта 2014 на Wayback Machine.
• 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, 176 (1), Princeton University and Institute for Advanced Study: 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, vol. 152, Springer-Verlag, pp. 83–93.