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