Interested Article - Гипотеза Хирша

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

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

Для $d$ -мерного выпуклого многогранника с $n$ гранями, граф , образованный его ребрами и вершинами, имеет диаметр не больше $n-d$ .

То есть любые две вершины многогранника можно соединить друг с другом по цепочке из не более чем $n-d$ рёбер.

Гипотеза была сформулирована в письме Джорджу Данцигу в 1957 году.
- Мотивация пришла из анализа симплекс-метода в линейном программировании .
Хирш доказал гипотезу в размерности 3, а также в нескольких частных случаях.
Известно, что верхняя оценка субэкспоненциальна по $n$ и $d$ .
В мае 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 (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 : , doi : , MR .
Klee, Victor; Walkup, David W. (1967), "The d -step conjecture for polyhedra of dimension d < 6", Acta Mathematica , 133 : 53—78, doi : , MR .
Miranda, Eva (2012), (PDF) , (86): 31—36 от 20 марта 2014 на Wayback Machine .
Naddef, Denis (1989), "The Hirsch conjecture is true for (0,1)-polytopes", , 45 (1): 109—110, doi : , MR .
Santos, Francisco (2011), "A counterexample to the Hirsch conjecture", Annals of Mathematics , Princeton University and Institute for Advanced Study, 176 (1): 383—412, arXiv : , doi : , MR
Ziegler, Günter M. (1994), "The Hirsch Conjecture", Lectures on Polytopes , Graduate Texts in Mathematics, vol. 152, Springer-Verlag, pp. 83—93 .