Гипотеза Хирша — опровергнутая гипотеза о диаметре графа многогранника, предполагала, что для -мерного выпуклого многогранника с гранями, граф, образованный его рёбрами и вершинами, имеет диаметр не больше (то есть любые две вершины многогранника можно соединить друг с другом по цепочке из не более чем рёбер).
Сформулирована в письме Джорджу Данцигу в 1957 году, предположение возникло по результатам анализа симплекс-метода в линейном программировании. Хирш доказал гипотезу в размерности 3, а также в нескольких частных случаях.
Известно, что верхняя оценка субэкспоненциальна по и .
В мае 2010 года Франсиско Сантос Леал предъявил контрпример — 43-мерный многогранник с 86 гранями и диаметром графа, превышающим 43. Вопрос о существовании линейной или полиномиальной оценки по состоянию остаётся открытым.
Литература . Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
. . . .
.
Категория:Опровергнутые математические гипотезы Категория:Комбинаторная геометрия