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


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

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

Для 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.
    • Вопрос о существовании линейной или полиномиальной оценки остаётся открытым.





Яндекс.Метрика