Гипотеза Хирша - Hirsch conjecture

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

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

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

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

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

В график выпуклого многогранник ${\displaystyle P}$ есть ли график чьи вершины находятся в биекция с вершинами ${\displaystyle P}$ таким образом, что любые две вершины графа соединяются ребром тогда и только тогда, когда две соответствующие вершины графа ${\displaystyle P}$ соединены ребром многогранника. В диаметр из ${\displaystyle P}$, обозначенный ${\displaystyle \delta (P)}$, - диаметр любого из его графиков. Эти определения четко определенный так как любые два графа одного многогранника должны быть изоморфный в виде графиков. Тогда мы можем сформулировать гипотезу Хирша следующим образом:

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

Например, куб в трех измерениях имеет шесть граней. Гипотеза Хирша показывает, что диаметр этого куба не может быть больше трех. Принятие гипотезы означало бы, что любые две вершины куба могут быть соединены дорожка от вершины к вершине с использованием не более трех шагов. Для всех многогранников размерности не менее 8 эта оценка фактически оптимальна; нет многогранника размерности ${\displaystyle d\geq 8}$ имеет диаметр меньше чем н-д, с п число его граней, как и раньше.^[10] Другими словами, почти для всех случаев гипотеза дает минимальное количество шагов, необходимых для соединения любых двух вершин многогранника путем по его ребрам. Поскольку симплексный метод по сути, работает путем построения пути из некоторой вершины возможный регион до оптимальной точки гипотеза Хирша предоставит нижнюю границу, необходимую для завершения симплекс-метода в худшем случае.

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

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

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

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

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

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

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

Контрпример

В октаэдр - один из самых известных примеров шпинделя.

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

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

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

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

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

Примечания

1. Зиглер (1994), п. 84.
2. Данциг (1963), стр.160 и 168.
3. Например. видеть Наддеф (1989) для многогранников 0-1.
4. Калаи и Клейтман (1992).
5. Сантос (2011).
6. Калаи (2010).
7. "Francisco Santos encuentra un contraejemplo que refuta la Congetura de Hirsch", Gaussianos, 24 мая 2010 г.
8. Сантос (2011)
9. Кли и Уолкап (1967).
10. Зиглер (1994)
11. Зиглер (1994)
12. Зиглер (1994)
13. Сантос (2011)
14. Сантос (2011)

Рекомендации

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