Гипотеза Хадвигера (комбинаторная геометрия)

Смотрите также: гипотеза Хадвигера (теория графов)

Треугольник может быть покрыт тремя меньшими копиями самого себя; квадрат требует четырех копий меньшего размера

Нерешенная задача по математике :

Может ли каждый $n$-мерное выпуклое тело, покрытое $2^{n}$ уменьшенные копии самого себя?

(еще нерешенные задачи по математике)

В комбинаторной геометрии гипотеза Хадвигера утверждает, что любое выпуклое тело в n -мерном евклидовом пространстве может быть покрыто 2 ^н или меньше меньших тел, гомотетичных исходному телу, и что, кроме того, верхняя граница 2 ^н необходимо тогда и только тогда, когда тело представляет собой параллелепипед . Существует также эквивалентная формулировка с точки зрения количества прожекторов, необходимых для освещения тела.

Гипотеза Хадвигера названа в честь Хьюго Хадвигера , который включил ее в список нерешенных проблем в 1957 году; однако ранее его изучали Леви (1955) и независимо Гохберг и Маркус (1960) . Кроме того, существует другая гипотеза Хадвигера, касающаяся раскраски графов , и в некоторых источниках геометрическая гипотеза Хадвигера также называется гипотезой Леви-Хадвигера или проблемой покрытия Хадвигера-Леви .

Гипотеза остается нерешенной даже в трех измерениях, хотя двумерный случай был решен Леви (1955) .

Официальное заявление

Формально гипотеза Хадвигера такова: если K — любое ограниченное выпуклое множество в n -мерном евклидовом пространстве R ^н , то существует набор из 2 ^н скаляры s _i и набор из 2 ^н векторы перемещения v _i такие, что все s _i лежат в диапазоне 0 < s _i < 1, и

$K\subseteq \bigcup _{i=1}^{2^{n}}s_{i}K+v_{i}.$

Более того, верхняя оценка необходима тогда и только тогда, когда K — параллелепипед, и в этом случае все 2 ^н скаляров можно выбрать равным 1/2.

Альтернативная формулировка с подсветкой

Как показал Болтянский , задача эквивалентна задаче об освещении: сколько прожекторов нужно разместить снаружи непрозрачного выпуклого тела, чтобы полностью осветить его снаружи? Для целей данной задачи тело считается освещенным только в том случае, если для каждой точки границы тела существует хотя бы один прожектор, отделенный от тела всеми касательными плоскостями, пересекающими тело в этой точке. ; таким образом, хотя грани куба могут быть освещены только двумя прожекторами, плоскости, касающиеся его вершин и краев, заставляют его нуждаться в гораздо большем количестве источников света, чтобы он был полностью освещен. Для любого выпуклого тела количество прожекторов, необходимых для его полного освещения, оказывается равным числу меньших копий тела, необходимых для его покрытия.

Примеры

Как показано на рисунке, треугольник может быть покрыт тремя меньшими копиями самого себя, и, в более общем смысле, в любом измерении симплекс может быть покрыт n + 1 копиями самого себя, масштабированными с коэффициентом n /( n + 1). Однако для покрытия квадрата меньшими квадратами (со сторонами, параллельными оригиналу) требуется четыре меньших квадрата, поскольку каждый из них может покрыть только один из четырех углов большего квадрата. В более высоких измерениях для покрытия гиперкуба или, в более общем смысле, параллелепипеда меньшими гомотетическими копиями той же формы требуется отдельная копия для каждой вершины исходного гиперкуба или параллелепипеда; потому что у этих фигур 2 ^н вершины, 2 ^н необходимы копии меньшего размера. Этого числа также достаточно: куб или параллелепипед можно покрыть двумя ^н копий, масштабированных с коэффициентом 1/2. Гипотеза Хадвигера состоит в том, что параллелепипеды являются наихудшим случаем для этой задачи и что любое другое выпуклое тело может быть покрыто менее чем двумя ^н уменьшенные копии самого себя.

Известные результаты

Двумерный случай был решен Леви (1955) : каждое двумерное ограниченное выпуклое множество может быть покрыто четырьмя меньшими копиями самого себя, причем четвертая копия необходима только в случае параллелограммов. Однако в более высоких измерениях гипотеза остается открытой, за исключением некоторых особых случаев. Самая известная асимптотическая верхняя граница числа меньших копий, необходимых для покрытия данного тела, равна

$\displaystyle 4^{n}\exp \left({\frac {-cn}{\log(n)}}\right)$

где $c$ является положительной константой. Для маленьких $n$ верхняя граница $(n+1)n^{n-1}-(n-1)(n-2)^{n-1}$ установленный Лассаком (1988), лучше асимптотического. Известно, что в трех измерениях всегда достаточно 16 копий, но это еще далеко от предполагаемой границы в 8 копий.

Известно, что гипотеза верна для некоторых специальных классов выпуклых тел, включая в размерности три центрально-симметричные многогранники и тела постоянной ширины . Число копий, необходимое для покрытия любого зонотопа (кроме параллелепипеда), не превышает $(3/4)2^{n}$, а для тел с гладкой поверхностью (т. е. имеющих одну касательную плоскость на каждую граничную точку) не более $n+1$ меньшие экземпляры необходимы для покрытия тела, как Леви . уже доказал

См. также

• Гипотеза Борсука о покрытии выпуклых тел множествами меньшего диаметра.

Ссылки

• Болтянский, В.; Гоберг, Израиль (1985), «11. Гипотеза Хадвигера», Результаты и проблемы комбинаторной геометрии , Cambridge University Press , стр. 44–46 .
• Брасс, Питер; Мозер, Уильям; Пах, Янош (2005), «3.3 Проблема покрытия Леви-Хадвигера и освещение», Проблемы исследования в дискретной геометрии , Springer-Verlag, стр. 136–142 .
• Кампос, Марсело; ван Хинтум, Питер; Моррис, Роберт ; Тиба, Мариус (2023), «К гипотезе Хадвигера посредством разрезания Бургейна», Международные уведомления о математических исследованиях , arXiv : 2206.11227 , doi : 10.1093/imrn/rnad198 .
• Гоберг, Израиль Ц. ; Маркус, Александр С. (1960), «Одна задача о покрытии выпуклых множеств гомотетическими», Известия Молдавского филиала Академии наук СССР (на русском языке), 10 (76): 87–90 .
• Хадвигер, Хьюго (1957), «Нерешенные проблемы № 20», «Элементы математики» , 12 : 121 .
• Хуан, Хан; Сломка, Боаз А.; Ткоч, Томаш; Врициу, Беатрис-Хелен (2022), «Улучшенные оценки проблемы покрытия Хадвигера с помощью оценок тонкой оболочки», Журнал Европейского математического общества , 24 (4): 1431–1448, arXiv : 1811.12548 , doi : 10.4171/jems/1132 , ISSN   1435-9855 .
• Лассак, Марек (1988), «Покрытие границы выпуклого множества плитками», Proceedings of the American Mathematical Society , 104 (1): 269–272, doi : 10.1090/s0002-9939-1988-0958081-7 , MR   0958081 .
• Леви, Фридрих Вильгельм (1955), «Покрытие области яйца параллельными смещениями его открытого ядра», Archives of Mathematics , 6 (5): 369–370, doi : 10.1007/BF01900507 , S2CID   121459171 .