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

[deep blue]

Lia в сообщении #1309895 писал(а):

У Вас пока ни турнира, ни тем более конечного числа вершин.

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

[Lia]

deep blue в сообщении #1311362 писал(а):

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

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

[deep blue]

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

[mihaild]

(Оффтоп)

Lia в сообщении #1311373 писал(а):

Ссылку с точной цитатой, пожалуйста.

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

[Lia]

(Оффтоп)

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

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

[glukmaker]

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

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

[arseniiv]

А где вы такую величину видели?

[glukmaker]

arseniiv в сообщении #1317586 писал(а):

А где вы такую величину видели?

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

[arseniiv]

glukmaker в сообщении #1317588 писал(а):

которое понятно что стремится к нулю, но не может быть равно ему

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

[grizzly]

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

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

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

-- 06.06.2018, 23:53 --

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

[glukmaker]

grizzly в сообщении #1317718 писал(а):

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

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

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

-- 06.06.2018, 23:53 --

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

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

[grizzly]

glukmaker в сообщении #1317794 писал(а):

(это можно доказать отдельно)

Хорошо, докажите.

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

[glukmaker]

grizzly писал(а):

Вопрос: а вы сможете доказать, что при таких условиях 7 цветов будет достаточно?

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

grizzly в сообщении #1317803 писал(а):

glukmaker в сообщении #1317794 писал(а):

(это можно доказать отдельно)

Хорошо, докажите.

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

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

[grizzly]

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

glukmaker в сообщении #1317806 писал(а):

А вот стоит ли это делать

Если только для того, чтобы сделать великое открытие -- тогда нет, точно не стоит. Но вообще стоит.