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

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

Нерешенная задача по математике : Можно ли покрыть каждое -мерное выпуклое тело меньшими копиями самого себя?${\ displaystyle n}$${\ Displaystyle 2 ^ {п}}$ (больше нерешенных задач по математике)

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

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

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

Официальное заявление [ править ]

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

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

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

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

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

Примеры [ править ]

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

Известные результаты [ править ]

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

${\ displaystyle \ displaystyle 4 ^ {n} (5n \ ln n).}$

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Болтянский, В .; Gohberg, Israel (1985), "11. Гипотеза Хадвигера", Результаты и проблемы комбинаторной геометрии , Cambridge University Press , стр. 44–46..
• Брасс, Питер; Мозер, Уильям; Пах, Янош (2005), "3.3 Проблема покрытия Леви – Хадвигера и освещение", Проблемы исследования в дискретной геометрии , Springer-Verlag, стр. 136–142..
• Гохберг, Израиль Ц. ; Маркус, Александр С. (1960), "Одна задача о покрытии выпуклых множеств гомотетическими", Известия Молдавского Филиала Академии Наук СССР , 10 (76): 87–90..
• Хадвигер, Хьюго (1957), "Ungelöste Probleme Nr. 20", Elemente der Mathematik , 12 : 121.
• Лассак, Марек (1988), «Покрытие границы выпуклого множества плитками», Труды Американского математического общества , 104 (1): 269–272, DOI : 10.1090 / s0002-9939-1988-0958081-7 , MR  0958081.
• Леви, Фридрих Вильгельм (1955), "Überdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns", Archiv der Mathematik , 6 (5): 369–370, doi : 10.1007 / BF01900507.