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

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

В математическом программировании и полиэдральной комбинаторике гипотеза Хирша — это утверждение, что ребер и вершин граф многогранника n - гранного не в d - мерном евклидовом пространстве имеет диаметр более n − d . То есть любые две вершины многогранника должны быть соединены друг с другом путем длиной не более n - d . Гипотеза была впервые высказана в письме Уоррена М. Хирша. Джорджу Б. Данцигу в 1957 году. и был мотивирован анализом симплекс- метода в линейном программировании , поскольку диаметр многогранника обеспечивает нижнюю границу количества шагов, необходимых для симплекс-метода. Теперь известно, что эта гипотеза в целом ошибочна.

Гипотеза Хирша была доказана для d < 4 и для различных частных случаев: в то время как наиболее известные верхние границы диаметра являются лишь субэкспоненциальными по n и d . объявил противоположный пример Спустя более чем пятьдесят лет в мае 2010 года Франсиско Сантос Леал из Университета Кантабрии . Результат был представлен на конференции « 100 лет в Сиэтле: математика Клее и Грюнбаума» и появился в «Анналах математики» . В частности, в статье представлен 43-мерный многогранник из 86 граней диаметром более 43. Контрпример не имеет прямых последствий для анализа симплекс-метода, так как не исключает возможности более крупного, но все же линейного или полиномиальное число шагов.

Были даны различные эквивалентные формулировки проблемы, такие как гипотеза о d -шаге, которая утверждает, что диаметр любого 2 -мерного многогранника в d -мерном евклидовом пространстве не превышает d ; Контрпример Сантоса Леала также опровергает эту гипотезу.

Формулировка гипотезы

График ​ выпуклого многогранника $P$ – это любой граф , вершины которого совпадают с вершинами $P$ таким образом, что любые две вершины графа соединены ребром тогда и только тогда, когда две соответствующие вершины графа $P$ соединены ребром многогранника. Диаметр ​ ​ $P$, обозначенный $\delta (P)$, — диаметр любого из его графиков. Эти определения четко определены , поскольку любые два графа одного и того же многогранника должны быть изоморфны как графы. Тогда мы можем сформулировать гипотезу Хирша следующим образом:

Гипотеза Пусть $P$ — d -мерный выпуклый многогранник с n гранями. Затем $\delta (P)\leq n-d$.

Например, трехмерный куб имеет шесть граней. Гипотеза Хирша тогда указывает на то, что диаметр этого куба не может быть больше трех. Принятие этой гипотезы означало бы, что любые две вершины куба могут быть соединены путем от вершины к вершине, используя не более трех шагов. Для всех многогранников размерности не менее 8 эта оценка фактически оптимальна; нет многогранника размерности $d\geq 8$ имеет диаметр меньше nd , где n — количество его граней, как и раньше. Другими словами, почти для всех случаев гипотеза обеспечивает минимальное количество шагов, необходимых для соединения любых двух вершин многогранника путем вдоль его ребер. Поскольку симплексный метод по существу работает путем построения пути от некоторой вершины допустимой области до оптимальной точки, гипотеза Хирша обеспечит нижнюю границу, необходимую для завершения симплексного метода в наихудшем сценарии.

Гипотеза Хирша является частным случаем полиномиальной гипотезы Хирша , которая утверждает, что существует некоторое положительное целое число k такое, что для всех многогранников $P$, $\delta (P)=O(n^{k})$, где n — количество граней P .

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

Гипотеза Хирша подтвердилась в ряде случаев. Например, любой многогранник размерностью 3 или меньше удовлетворяет этой гипотезе. Любой d -мерный многогранник с n гранями такой, что $n-d\leq 6$ также удовлетворяет гипотезе.

Другие попытки решить эту гипотезу были вызваны желанием сформулировать другую задачу, решение которой подразумевало бы гипотезу Хирша. Одним из примеров особой важности является гипотеза d-шага , ослабление гипотезы Хирша, эквивалентность которой фактически была доказана.

Теорема Следующие утверждения эквивалентны:

1. $\delta (P)\leq n-d$ для всех d -мерных многогранников $P$ с n гранями.
2. $\delta (P)\leq d$ для всех d -мерных многогранников $P$ с 2d гранями.

Другими словами, чтобы доказать или опровергнуть гипотезу Хирша, достаточно рассмотреть многогранники, число граней которых ровно в два раза превышает его размерность. Другое существенное послабление состоит в том, что гипотеза Хирша справедлива для всех многогранников тогда и только тогда, когда она справедлива для всех простых многогранников .

Контрпример

Октаэдр — один из самых известных примеров веретена.

К сожалению, гипотеза Хирша верна не во всех случаях, как показал Франсиско Сантос в 2011 году. Явное построение Сантосом контрпримера проистекает как из того факта, что гипотезу можно ослабить, чтобы рассматривать только простые многогранники, так и из эквивалентности между гипотезой Хирша и гипотезы d -шага. В частности, Сантос приводит свой контрпример, исследуя особый класс многогранников, называемых веретенами .

Определение. d - веретено — это d -мерный многогранник. $P$ для которого существует пара различных вершин, такая что каждая грань $P$ содержит ровно одну из этих двух вершин.

Длина кратчайшего пути между этими двумя вершинами называется длиной веретена. Опровержение гипотезы Хирша основано на следующей теореме, называемой сильной теоремой о d-шаге для веретен .

Теорема (Сантоса) Пусть $P$ быть d -веретеном. Пусть n — количество его граней, а l — его длина. Тогда существует $(n-d)$- шпиндель, $P'$, с $2n-2d$ граней и длину, ограниченную снизу $l+n-2d$. В частности, если $l>d$, затем $P'$ нарушает гипотезу d -шага.

Затем Сантос приступает к построению 5-мерного веретена длиной 6, доказывая тем самым, что существует другое веретено, которое служит контрпримером к гипотезе Хирша. Первое из этих двух веретен имеет 48 граней и 322 вершины, тогда как веретено, которое фактически опровергает гипотезу, имеет 86 граней и является 43-мерным. Этот контрпример не опровергает полиномиальную гипотезу Хирша, которая остается открытой проблемой.

Ссылки

• Данциг, Джордж Б. (1963), Линейное программирование и расширения , Princeton Univ. Нажимать . Перепечатано в серии Princeton Landmarks in Mathematics , Princeton University Press, 1998.
• Калаи, Гил (10 мая 2010 г.). «Франсиско Сантос опровергает гипотезу Хирша» . Проверено 11 мая 2010 г.
• Калай, Гил ; Клейтман, Дэниел Дж. (1992), «Квазимолиномиальная оценка диаметра графов многогранников», Бюллетень Американского математического общества , 26 (2): 315–316, arXiv : math/9204233 , doi : 10.1090/ S0273-0979-1992-00285-9 , MR   1130448 , S2CID   37821778 .
• Клее, Виктор ; Уолкап, Дэвид В. (1967), « Гипотеза d -шага для многогранников размерности d <6», Acta Mathematica , 133 : 53–78, doi : 10.1007/BF02395040 , MR   0206823 .
• Миранда, Ева (2012), «Гипотеза Хирша опровергнута: интервью с Франсиско Сантосом» (PDF) , Информационный бюллетень Европейского математического общества (86): 31–36 .
• Наддеф, Денис (1989), «Гипотеза Хирша верна для (0,1)-многогранников», Mathematical Programming , 45 (1): 109–110, doi : 10.1007/BF01589099 , MR   1017214 , S2CID   24632864 .
• Сантос, Франциско (2011), «Контрпример к гипотезе Хирша», Annals of Mathematics , 176 (1), Принстонский университет и Институт перспективных исследований: 383–412, arXiv : 1006.2814 , doi : 10.4007/annals.2012.176.1.7 , МР   2925387 , S2CID   15325169
• Циглер, Гюнтер М. (1994), «Гипотеза Хирша», Лекции по многогранникам , Тексты для аспирантов по математике, том. 152, Springer-Verlag, стр. 83–93 .