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

• Гипотеза Хирша в математическом программировании

  • Гипотеза утверждает, что диаметр реберно-вершинного графа n-гранного многогранника не превышает n − d. 
  • Впервые высказана в 1957 году и мотивирована анализом симплекс-метода. 
  • Известна как ложная в целом, но доказана для d < 4 и некоторых частных случаев. 

• Контрпример Сантоса Леала

  • В 2010 году Сантос Леал представил 43-мерный многогранник с диаметром более 43, опровергая гипотезу. 
  • Контрпример не влияет на анализ симплекс-метода, так как не исключает возможности линейного или полиномиального числа шагов. 

• Формулировка и эквивалентности

  • Гипотеза позволяет определить диаметр как диаметр любого из графов многогранника. 
  • Эквивалентна гипотезе о d-шаге и теореме о сильной теореме о d-шаге для шпинделей. 

• Прогресс и промежуточные результаты

  • Гипотеза доказана для многогранников размерностью 3 и ниже, а также для некоторых частных случаев. 
  • Существуют попытки решить гипотезу, включая гипотезу d-шага. 

• Ослабления гипотезы

  • Гипотеза верна для всех многогранников, если верна для всех простых многогранников. 

• Теорема Сантоса

  • Сантос использовал теорему о сильной теореме о d-шаге для шпинделей, чтобы построить контрпример. 
  • Контрпример представляет собой 43-мерное веретено с 86 гранями, нарушающее гипотезу Хирша.