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

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

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

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

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

Литература

• Шаблон:Citation. Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
• Шаблон:Cite web
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation Шаблон:Wayback.
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation.