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

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

Формулировка

Для [math]\displaystyle{ d }[/math]-мерного выпуклого многогранника с [math]\displaystyle{ n }[/math] гранями, граф, образованный его ребрами и вершинами, имеет диаметр не больше [math]\displaystyle{ n-d }[/math].

То есть любые две вершины многогранника можно соединить друг с другом по цепочке из не более чем [math]\displaystyle{ n-d }[/math] рёбер.

История

• Гипотеза была сформулирована в письме Уоррена Хирша Джорджу Данцигу в 1957 году.
  • Мотивация пришла из анализа симплекс-метода в линейном программировании.
• Хирш доказал гипотезу в размерности 3, а также в нескольких частных случаях.
• Известно, что верхняя оценка субэкспоненциальна по [math]\displaystyle{ n }[/math] и [math]\displaystyle{ d }[/math].
• В мае 2010 года Франсиско Сантос Леал предъявил контрпример — 43-мерный многогранник с 86 гранями и диаметром графа, превышающим 43.
  • Вопрос о существовании линейной или полиномиальной оценки остаётся открытым.

Литература

• 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, DOI 10.1090/S0273-0979-1992-00285-9 .
• 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 .
• Miranda, Eva (2012), The Hirsch conjecture has been disproved: An interview with Francisco Santos, Newsletter of the European Mathematical Society (no. 86): 31–36, <http://www.ems-ph.org/journals/newsletter/pdf/2012-12-86.pdf>  Архивная копия от 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 .
• Santos, Francisco (2011), A counterexample to the Hirsch conjecture, Annals of Mathematics (Princeton University and Institute for Advanced Study) . — Т. 176 (1): 383–412, DOI 10.4007/annals.2012.176.1.7 
• Ziegler, Günter M. (1994), The Hirsch Conjecture, Lectures on Polytopes, vol. 152, Graduate Texts in Mathematics, Springer-Verlag, с. 83–93 .