2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5  След.
 
 Задача Нелсона-Хадвигера
Сообщение27.04.2018, 15:51 


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

Формулировка: каково хроматические число метрического пространства по отношению к запрещенному расстоянию 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 вершинами).

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

 Профиль  
                  
 
 Posted automatically
Сообщение27.04.2018, 22:44 
Супермодератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение28.04.2018, 16:05 
Супермодератор
Аватара пользователя


09/05/12
20735
Кронштадт
 i  Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 16:09 
Экс-модератор
Аватара пользователя


23/12/05
11530
EvgenyNechaev в сообщении #1307962 писал(а):
ровно 7 различных цветов, 1 в центре и 6 на окружности

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 16:15 


27/04/18
40
photon в сообщении #1308357 писал(а):
EvgenyNechaev в сообщении #1307962 писал(а):
ровно 7 различных цветов, 1 в центре и 6 на окружности

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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 16:18 
Заслуженный участник
Аватара пользователя


16/07/14
3853
Москва
EvgenyNechaev в сообщении #1307962 писал(а):
но другими цветовыми оттенками
Что за оттенки? Просто цвета?
Почему точки, переходящие друг в друга при повороте на $1$ радиан, имеют разные цвета, понятно. Почему это верно для точек, переходящих друг в друга при повороте на $2$?

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 16:19 
Экс-модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 16:39 


27/04/18
40
mihaild в сообщении #1308361 писал(а):
EvgenyNechaev в сообщении #1307962 писал(а):
но другими цветовыми оттенками
Что за оттенки? Просто цвета?

Нет, цвета составленные из ровно двух других цветов. Ведь мы получаем их наложением двух крат друг на друга.
mihaild в сообщении #1308361 писал(а):
EvgenyNechaev в сообщении #1307962 писал(а):
но другими цветовыми оттенками
Почему это верно для точек, переходящих друг в друга при повороте на $2$?

Не понял вопрос, мы не поворачиваем на 2.
mihaild в сообщении #1308361 писал(а):
EvgenyNechaev в сообщении #1307962 писал(а):
но другими цветовыми оттенками

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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 16:49 
Заслуженный участник
Аватара пользователя


16/07/14
3853
Москва
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 писал(а):
Нет, цвета составленные из ровно двух других цветов.
Т.е. по-русски - это пара цветов? Упорядоченная или нет?

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 16:50 


27/04/18
40
photon в сообщении #1308362 писал(а):
Что вы называете оттенками, чем они отличаются от цветов

Цвет составленный ровно из двух других цветов и полученный наложением двух карт друг на друга и их вращением.
photon в сообщении #1308362 писал(а):
Откуда следует уникальность.

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

-- 28.04.2018, 18:59 --

mihaild в сообщении #1308370 писал(а):
EvgenyNechaev в сообщении #1308367 писал(а):
Не понял вопрос, мы не поворачиваем на 2.

Что еще?

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

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 17:22 
Заслуженный участник
Аватара пользователя


16/07/14
3853
Москва
EvgenyNechaev в сообщении #1308371 писал(а):
Ещё нужно понимать что мы не крутим, а идём шагами равными запрещённому расстоянию 1.
Ок, тогда я вообще не понимаю, что вы пытаетесь сделать. Особенно с учетом
EvgenyNechaev в сообщении #1307962 писал(а):
Так как вращать мы можем только с шагом 1


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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 17:57 


27/04/18
40
mihaild в сообщении #1308377 писал(а):
Давайте с самого начала. Пусть $f$ - раскраска плоскости в $6$ цветов. Цвета пронумеруем: $1, 2, 3, 4, 5, 6$. Что дальше?

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 18:01 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 18:23 


27/04/18
40
mihaild в сообщении #1308386 писал(а):
что такое "эпсилон-окрестность в данном случае" непонятно.

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

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение28.04.2018, 18:37 
Заслуженный участник
Аватара пользователя


16/07/14
3853
Москва
EvgenyNechaev в сообщении #1308389 писал(а):
Правильный шестиугольник с длиной стороны равной запрещённому расстоянию.
Который? На плоскости континуальное число шестиугольников с данной длиной стороны. Наверное он должен быть как-то связан с какой-то точкой (раз уж вы говорите про "окрестность точки"), но даже таких всё еще континуум.
Я же вам даже привел пример определения, попробуйте воспроизвести что-то подобное.
(когда сформулируете определение - пишите следующий шаг)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 74 ]  На страницу 1, 2, 3, 4, 5  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group