Задача Нелсона-Хадвигера

[EvgenyNechaev]

Как мне кажется, я решил одну из наиболее известных задач комбинаторики, задачу Нелсона-Хадвигера о хроматическом числе метрического пространства для плоскости и трехмерного пространства.

Формулировка: каково хроматические число метрического пространства по отношению к запрещенному расстоянию 1?

Ответ для двухмерной плоскости: хроматическое число двухмерной плоскости равно целой части отношения длины окружности к её диаметру, вычисленного с точностью равной количеству порядков частного запрещённого расстояния от расстояния плюс один, то есть $2 \cdot 3 \cdot 1 + 1 = 7$ для расстояния между точками 1 и запрещённого расстояния 1 и т.д.

Ответ для трехмерного пространства: $4 \cdot 3 \cdot 1 + 1 = 13$ для расстояния между точками 1 и запрещённого расстояния 1 и т.д.

Как это у меня получилось? До элементарного просто. Вдумаемся в понятие "запрещённое расстояние". Что это? В контексте задачи - минимально допустимое расстояние между двумя точками или, неформально, верхний предел размера эпсилон-окрестности точки. Иными словами, длина окружности запрещённого расстояния радиуса 1 в максимальном приближении равна шести или, говоря ещё проще, любые расстояния меньше 1 не считаются и приравниваются к нолю.

Известно, что хроматическое число плоскости равно 5 или 6 или 7 (надеюсь, все читали недавнюю работу Обри ди Грея). Покажем, что 5 и 6 цветов для раскраски плоскости недостаточно. Допустим, что такая карта существует. В таком случае, если взять на ней две точки, находящиеся на запрещённом расстоянии 1 и начать вращать карту вокруг одной из них (точки-оси), то наложение получившихся карт друг на друга будет давать новую карту с идентичным свойством, но другими цветовыми оттенками, до тех пор, пока не будет совершён полный оборот вокруг точки-оси. Так как вращать мы можем только с шагом 1, то очевидно, что для полного оборота нам понадобится ровно 6 шагов, то есть на конечной карте будет ровно 7 различных цветов, 1 в центре и 6 на окружности запрещённого расстояния. Аналогично решается задача раскраски трёхмерного пространства, разница лишь в том, что там выйдет не круг замощённый 6 треугольниками, а шар с 20 правильными тетраэдрами (икосаэдр с 12 вершинами).

Всё равно непонятно? Готов ответить на любые вопросы Сообщества.

[Pphantom]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»

[photon]

EvgenyNechaev в сообщении #1307962 писал(а):

ровно 7 различных цветов, 1 в центре и 6 на окружности

А почему эти 6 должны быть все различны? А что будет если в центре один цвет, а по кругу еще два через один?

[EvgenyNechaev]

photon в сообщении #1308357 писал(а):

EvgenyNechaev в сообщении #1307962 писал(а):

ровно 7 различных цветов, 1 в центре и 6 на окружности

А почему эти 6 должны быть все различны?

Потому что каждый оттенок имеет свой уникальный цвет

[mihaild]

EvgenyNechaev в сообщении #1307962 писал(а):

но другими цветовыми оттенками

Что за оттенки? Просто цвета?
Почему точки, переходящие друг в друга при повороте на $1$ радиан, имеют разные цвета, понятно. Почему это верно для точек, переходящих друг в друга при повороте на $2$?

Я правильно понимаю, что вы предлагаете формулу $\lceil S_n\rceil + 1$ для $n$-мерного пространства? ($S_n$ - площадь поверхности $n$-мерной сферы радиуса $1$) Тогда учтите, что начиная с размерности $18$ площадь поверхности сферы меньше радиуса.

[photon]

Из вашего поста непонятно: 1) Что вы называете оттенками, чем они отличаются от цветов; 2) Откуда следует уникальность.

[EvgenyNechaev]

mihaild в сообщении #1308361 писал(а):

EvgenyNechaev в сообщении #1307962 писал(а):

но другими цветовыми оттенками

Что за оттенки? Просто цвета?

Нет, цвета составленные из ровно двух других цветов. Ведь мы получаем их наложением двух крат друг на друга.

mihaild в сообщении #1308361 писал(а):

EvgenyNechaev в сообщении #1307962 писал(а):

но другими цветовыми оттенками

Почему это верно для точек, переходящих друг в друга при повороте на $2$?

Не понял вопрос, мы не поворачиваем на 2.

mihaild в сообщении #1308361 писал(а):

EvgenyNechaev в сообщении #1307962 писал(а):

но другими цветовыми оттенками

Я правильно понимаю, что вы предлагаете формулу $\lceil S_n\rceil + 1$ для $n$-мерного пространства?

Нет, неправильно. Общей формулы нет, я решил щадачу лишь для плоскости и трёхмерного пространства.

[mihaild]

EvgenyNechaev в сообщении #1308367 писал(а):

Не понял вопрос, мы не поворачиваем на 2.

Поворот на $2$ радиана - это два поворота на $1$ радиан.

Давайте с самого начала. Пусть у нас есть функция $f: \mathbb{R}^2 \to \{1,2,3,4,5,6\}$, задающая правильную раскраску. Взяли точку $(0, 0)$, крутим вокруг нее.
Скажем начали с точки $(1, 0)$. Поворачиваем, получаем последовательность точек $(\cos n, \sin n)$. Мы знаем, что $f(0, 0) \neq f(\cos n, \sin n) \neq f(\cos (n + 1), \sin(n + 1))$. Что еще?

EvgenyNechaev в сообщении #1308367 писал(а):

Нет, цвета составленные из ровно двух других цветов.

Т.е. по-русски - это пара цветов? Упорядоченная или нет?

[EvgenyNechaev]

photon в сообщении #1308362 писал(а):

Что вы называете оттенками, чем они отличаются от цветов

Цвет составленный ровно из двух других цветов и полученный наложением двух карт друг на друга и их вращением.

photon в сообщении #1308362 писал(а):

Откуда следует уникальность.

Потому что если оттенок не будет уникален, то легко получить карту для которой не соблюдено условие. Грубо говоря, взяв негатив с получившейся карты на Веретене Мозера будет всего три цвета, четвёртый будет одинаков с одним из трёх.

-- 28.04.2018, 18:59 --

mihaild в сообщении #1308370 писал(а):

EvgenyNechaev в сообщении #1308367 писал(а):

Не понял вопрос, мы не поворачиваем на 2.

Что еще?

Ещё нужно понимать что мы не крутим, а идём шагами равными запрещённому расстоянию 1.

Вопрос про упорядоченность пары цветов не понял, не хватает образования.

[mihaild]

EvgenyNechaev в сообщении #1308371 писал(а):

Ещё нужно понимать что мы не крутим, а идём шагами равными запрещённому расстоянию 1.

Ок, тогда я вообще не понимаю, что вы пытаетесь сделать. Особенно с учетом

EvgenyNechaev в сообщении #1307962 писал(а):

Так как вращать мы можем только с шагом 1

Давайте с самого начала. Пусть $f$ - раскраска плоскости в $6$ цветов. Цвета пронумеруем: $1, 2, 3, 4, 5, 6$. Что дальше?
Если вводите какую-то точку - пожалуйста, сразу обозначайте ее какой-то буквой, чтобы было понятно, где о чем речь; если говорите о новых понятиях - "цвета, составленные из других цветов" и т.д. - говорите, что это означает.

[EvgenyNechaev]

mihaild в сообщении #1308377 писал(а):

Давайте с самого начала. Пусть $f$ - раскраска плоскости в $6$ цветов. Цвета пронумеруем: $1, 2, 3, 4, 5, 6$. Что дальше?

Дальше вспомним про эпсилон-окрестность точки и поймём, что в данном случае она имеет форму правильного шестиугольника, а не круга

[mihaild]

EvgenyNechaev в сообщении #1308384 писал(а):

Дальше вспомним про эпсилон-окрестность точки и поймём, что в данном случае она имеет форму правильного шестиугольника, а не круга

Нет, не поймем. Определение (открытой) $\varepsilon$-окрестности точки $x$: множество таких точек $y$, что $\rho(x, y) < \varepsilon$. Это определение параметризовано двумя параметрами: точкой и размером окрестности; параметризации "случаем" там нет, так что что такое "эпсилон-окрестность в данном случае" непонятно.
Если хотите ввести определение "эпсилон-окрестности в данном случае" - вводите, только явно его выпишите. Например: $EN-\varepsilon$ окрестностью точки $x$ называются точки, лежащие в открытом шестиугольнике с центром в $x$, длиной стороны $\varepsilon$ и двумя сторонами, параллельными $Ox$ (я совершенно не настаиваю на этом определении, можете дать какое хотите; это просто пример, как оно могло бы выглядеть).
После введения определени(я,й) можно переходить к формулировкам каких-то утверждений.

[EvgenyNechaev]

mihaild в сообщении #1308386 писал(а):

что такое "эпсилон-окрестность в данном случае" непонятно.

Правильный шестиугольник с длиной стороны равной запрещённому расстоянию.

[mihaild]

EvgenyNechaev в сообщении #1308389 писал(а):

Правильный шестиугольник с длиной стороны равной запрещённому расстоянию.

Который? На плоскости континуальное число шестиугольников с данной длиной стороны. Наверное он должен быть как-то связан с какой-то точкой (раз уж вы говорите про "окрестность точки"), но даже таких всё еще континуум.
Я же вам даже привел пример определения, попробуйте воспроизвести что-то подобное.
(когда сформулируете определение - пишите следующий шаг)