2014 dxdy logo

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

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




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


23/11/09
173
Lia в сообщении #1309895 писал(а):
У Вас пока ни турнира, ни тем более конечного числа вершин.
Насколько мне известно хроматическое число плоскости равно максимуму среди хроматических чисел множества всех конечных графов (у которых вершины графа - точки плоскости, а ребра это единичные расстояния). Поэтому, наверное, без потери общности можно считать что граф у нас конечный.

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение10.05.2018, 08:03 
Модератор
Аватара пользователя


20/03/14
10557
deep blue в сообщении #1311362 писал(а):
Насколько мне известно хроматическое число плоскости равно максимуму среди хроматических чисел множества всех конечных графов

Ссылку с точной цитатой, пожалуйста.
Это во-первых.
Во-вторых, конструкция, излагаемая ТС, в том месте, откуда Вы взяли мою цитату, не подразумевала возможности "считать, что граф у нас конечный".

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


23/11/09
173
Lia Мне лень тратить время и искать какие-то ссылки за других, кому нужно пусть сам ищет. Я же не обязан это делать по правилам форума, правда? Тем более что никакой ссылки я никогда не видел, мне сообщил об этом авторитетный человек в приватной беседе.
Насчет возможности ТС считать что граф у нас конечный. Я не вдумывался какой граф предлагал в том месте ТС. Просто сообщил что сама задача Нелсона-Хадвигера подразумевает возможность считать что граф у нас конечный с самого начала. Если вершины графа - точки плоскости, а ребра - единичные расстояния.

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


16/07/14
3853
Москва

(Оффтоп)

Lia в сообщении #1311373 писал(а):
Ссылку с точной цитатой, пожалуйста.
А в чем тут проблема? Теорема де Брёйна - Эрдёша: граф можно раскрасить в $k$ цветов тогда и только тогда, когда каждый его конечный подграф можно раскрасить в $k$ цветов (при условии аксиомы выбора).

 Профиль  
                  
 
 Re: Задача Нелсона-Хадвигера
Сообщение10.05.2018, 16:14 
Модератор
Аватара пользователя


20/03/14
10557

(Оффтоп)

mihaild
Да боже мой, абсолютно ни в чем. Я попросила ссылку с цитатой, а не говорила что у меня проблемы.
deep blue
Вы ничего не обязаны, ведь правда? Однако зачем-то это делаете. И каждое Ваше действие способно повлечь за собой некоторые последствия. И было бы проще и познавательней - и быстрее, если бы Вы сослались на результат, а не на приватную беседу. Вот и все.

Всем спасибо.

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


30/06/14
47
Приношу извинения, за то что пользуюсь чужой темой, но думаю что ради одного вопроса нет смысла создавать новую.

Вопрос такой: можно ли считать доказательством некоей гипотезы о хроматическом числе плоскости доказательство со смягченным условием, а именно: если допустить, что запрещенное расстояние равно не только единице 1, а также:
$p=1\pm\xi$, где $\xi$ - величина, бесконечно приближающаяся к $0$, но не равная ему, т.е.:
$\xi=\frac{1}{x}$, $x\to+\infty$
?

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


27/04/09
27145
А где вы такую величину видели?

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


30/06/14
47
arseniiv в сообщении #1317586 писал(а):
А где вы такую величину видели?


под $\xi$ подразумевается минимальное расстояние между двумя точками с несовпадающими цветами (на закрашенной несколькими цветами плоскости), которое понятно что стремится к нулю, но не может быть равно ему.
Просто при таком подходе, я думаю что очень легко доказать хроматическое число плоскости не может быть менее $6$, и не нужно строить гигантских графов, как это делал Обри де Грей.

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


27/04/09
27145
glukmaker в сообщении #1317588 писал(а):
которое понятно что стремится к нулю, но не может быть равно ему
Число не может «стремиться, но не быть равным», это может делать функция (и в стандартном анализе бесконечно малыми и большими величинами называются как раз функции). Вы всё ещё уверены, что всё в порядке?

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


09/09/14
6190
Да ну ладно, вопрос понятно какой. Утверждается примерно следующее:
Пусть запрещено расстояние 1 и пусть для некоторого достаточно малого $\xi $ запрещены ещё два расстояния: $1\pm \xi$. Тогда потребуется не менее 6 фломастеров.

Затем предполагается устремить $\xi $ к нулю.

glukmaker,
Я правильно понял?

-- 06.06.2018, 23:53 --

Хотя нет, наверное запрещены все расстояния в промежутке $(1-\xi, 1+\xi)$.

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


30/06/14
47
grizzly в сообщении #1317718 писал(а):
Да ну ладно, вопрос понятно какой. Утверждается примерно следующее:
Пусть запрещено расстояние 1 и пусть для некоторого достаточно малого $\xi $ запрещены ещё два расстояния: $1\pm \xi$. Тогда потребуется не менее 6 фломастеров.

Затем предполагается устремить $\xi $ к нулю.

glukmaker,
Я правильно понял?

-- 06.06.2018, 23:53 --

Хотя нет, наверное запрещены все расстояния в промежутке $(1-\xi, 1+\xi)$.


Ну смысл такой: Если плоскость раскрашена в несколько цветов, то всегда существует граница между двумя цветами, и если допустим точка на этой границе имеет один цвет, то бесконечно малый сдвиг ее в сторону может поменять ее цвет.
На плоскости имеющей запрещенное расстояние должны находиться точки где сходятся как минимум 3 цвета (это можно доказать отдельно).
Проводим окружность запрещенного радиуса с центром в этой точке. Окружность должна иметь как минимум 2 других цвета не совпадающих с начальными тремя. А значит на окружности существуют места где сходятся как минимум 2 цвета, А это значит что второй конец хорды запрещенного расстояния, имеющий начало в этой точке имеет цвет не совпадающий ни с первыми тремя, ни со вторыми двумя. Т.е. цветов должно быть не менее 6.

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


09/09/14
6190
glukmaker в сообщении #1317794 писал(а):
(это можно доказать отдельно)
Хорошо, докажите.

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

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


30/06/14
47
grizzly писал(а):
Вопрос: а вы сможете доказать, что при таких условиях 7 цветов будет достаточно?


Зачем? Это же уже доказано всем известным примером с шестиугольниками 7 цветов. Кстати там запрещенное расстояние не является фиксированным числом, а является диапазоном, в котором отношение его максимального значения к минимальному равняется $\frac{\sqrt{7}}{2}$, т.е. это есть доказательство для довольно большого значения
$\xi=\frac{\sqrt{7}-2}{\sqrt{7}+2}\approx0.14$

grizzly в сообщении #1317803 писал(а):
glukmaker в сообщении #1317794 писал(а):
(это можно доказать отдельно)
Хорошо, докажите.


У меня в голове есть доказательство (Если кратко то граница соприкосновения 2 цветов на плоскости имеется всегда (очевидно), а наличие точки соприкосновения 3 цветов доказывается от противного). Правильное оно или нет, можно проверить опубликовавши его здесь, но видимо придется создавать новую тему. А вот стоит ли это делать если окажется что вышеупомянутое "смягчение условия" в данной задаче неуместно? Поэтому и интересуюсь заранее.

Есть одна проблема. При таком подходе, каким бы минимальным (разумеется положительным) ни бы величина $\xi$, но если она не равна нулю, то возникает проблема с хроматическим числом одномерного пространства (т.е. прямой)

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


09/09/14
6190
Да, насчёт 7 всё правильно, есть зазор в расстояниях.

glukmaker в сообщении #1317806 писал(а):
А вот стоит ли это делать
Если только для того, чтобы сделать великое открытие -- тогда нет, точно не стоит. Но вообще стоит.

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

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



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

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


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

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