Гипотеза Хадвигера (комбинаторная геометрия) - Hadwiger conjecture (combinatorial geometry) - Wikipedia

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

Нерешенная проблема в математике:

Может каждый

{ displaystyle n}

-мерное выпуклое тело покрывается

{ Displaystyle 2 ^ {п}}

уменьшенные копии самого себя?

(больше нерешенных задач по математике)

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

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

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

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

Формально гипотеза Хадвигера такова: если K есть ли ограниченный выпуклый набор в п-размерный Евклидово пространство р^п, то существует набор из 2^п скаляры s_я и набор из 2^п векторы перевода v_я так что все s_я лежат в диапазоне 0 <s_я <1, и

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

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

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

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

Примеры

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

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

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

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

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

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