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

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

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

Известно, что верхняя оценка субэкспоненциальна по $n$ и $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.