Проблема Хадвигера – Нельсона - Hadwiger–Nelson problem

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

Сколько цветов нужно, чтобы раскрасить плоскость, чтобы никакие две точки на единичном расстоянии не были одного цвета?

Семи-раскраска плоскости и четырехцветный граф единичных расстояний на плоскости ( Шпиндель Мозера ), доказывая, что хроматическое число плоскости ограничено сверху 7 и снизу 4.

В Граф Голомба, Соломон В. Голомб десятивершинный четырехцветный график единичного расстояния

В геометрическая теория графов, то Проблема Хадвигера – Нельсона, названный в честь Хьюго Хадвигер и Эдвард Нельсон, запрашивает минимальное количество цветов, необходимое для раскрашивания самолет такой, что нет двух точки на расстоянии 1 друг от друга имеют одинаковый цвет. Ответ неизвестен, но был сужен до одного из чисел 5, 6 или 7. Правильное значение может зависеть от выбора аксиом для теория множеств.^[1]

Связь с конечными графами

Вопрос можно сформулировать на теоретический график термины следующим образом. Позволять грамм быть график единичного расстояния плоскости: бесконечный граф со всеми точками плоскости как вершины и с ребром между двумя вершинами тогда и только тогда, когда расстояние между двумя точками равно 1. Задача Хадвигера – Нельсона состоит в том, чтобы найти хроматическое число из грамм. Как следствие, проблему часто называют «нахождение хроматического числа плоскости». Посредством Теорема де Брейна – Эрдеша, Результат де Брюйн и Эрдёш (1951), задача эквивалентна (в предположении аксиома выбора ) к поиску максимально возможного хроматического числа графа конечных единичных расстояний.

История

В соответствии с Дженсен и Тофт (1995), проблема была впервые сформулирована Нельсоном в 1950 г. и впервые опубликована Гарднер (1960). Хадвигер (1945) ранее опубликовал связанный результат, показывающий, что любое покрытие плоскости пятью конгруэнтными замкнутыми множествами содержит единичное расстояние в одном из множеств, и он также упомянул эту проблему в более поздней статье (Хадвигер 1961 ). Сойфер (2008) подробно обсуждает проблему и ее историю.

Нижняя и верхняя границы

Тот факт, что хроматическое число плоскости должно быть не менее четырех, следует из существования графа единичных расстояний с семью вершинами и хроматическим числом четыре, названного Шпиндель Мозера после его открытия в 1961 году братьями Уильямом и Лео Мозер. Этот граф состоит из двух единиц равносторонние треугольники соединены в общей вершине, Икс. Каждый из этих треугольников соединен по другому ребру с другим равносторонним треугольником; вершины у и z этих соединенных треугольников находятся на единичном расстоянии друг от друга. Если бы самолет мог быть трехцветным, раскраска внутри треугольников заставила бы у и z чтобы оба имели тот же цвет, что и Икс, но тогда, поскольку у и z находятся на единичном расстоянии друг от друга, у нас не будет правильной раскраски графа единичных расстояний на плоскости. Следовательно, необходимо как минимум четыре цвета, чтобы раскрасить этот граф и содержащую его плоскость. Альтернативная нижняя граница в виде четыреххроматического графа расстояний с десятью вершинами, Граф Голомба, был обнаружен примерно в то же время Соломон В. Голомб.^[2]

В 2018 году компьютерный ученый и биолог Обри де Грей нашел 1581-вершинный, не 4-раскрашиваемый граф единичных расстояний. Доказательство - компьютерная помощь.^[3] Математик Гил Калаи^[4] и компьютерный ученый Скотт Ааронсон^[5] опубликовал обсуждение открытия де Грея, где Ааронсон сообщил о независимых проверках результата де Грея, используя SAT решатели. Kalai добавил ссылки на дополнительные сообщения Джордан Элленберг и Ноам Элкис, где Элкис и (по отдельности) де Грей предложили Проект Polymath найти не 4-раскрашиваемые графы единичных расстояний с меньшим числом вершин, чем в конструкции де Грея. По состоянию на 2018 год самый маленький из известных графов с хроматическим числом 5 имел 553 вершины. Heule (2018), но в августе 2019 года Яан Партс нашел пример с 510 вершинами.^[6] Страница проекта Polymath, Полимат (2018), содержит дальнейшие исследования, ссылки в СМИ и данные проверки.

Верхняя граница семи для хроматического числа следует из существования мозаика плоскости правильными шестиугольниками диаметром чуть меньше единицы, которым можно присвоить семь цветов в повторяющемся узоре, чтобы сформировать 7-цветную окраску плоскости. В соответствии с Сойфер (2008), эта верхняя граница впервые была обнаружена Джон Р. Исбелл.

Варианты проблемы

Проблема может быть легко расширена на более высокие измерения. В частности, определение хроматического числа пространства обычно относится к трехмерной версии. Как и в случае с версией в самолете, ответ неизвестен, но было показано, что он должен быть от 6 до 15.^[7]

в п-мерный случай задачи, простая верхняя оценка количества требуемых раскрасок, найденных из тайлинга п-мерные кубики ${ displaystyle lfloor 2 + { sqrt {n}} rfloor ^ {n}}$ . Нижняя граница из симплексов равна ${ displaystyle n + 1}$ . За ${ displaystyle n> 1}$ , нижняя граница ${ displaystyle n + 2}$ доступен с использованием обобщения веретена Мозера: пара объектов (каждые 2 симплекса, склеенных вместе на фасете), которые соединены с одной стороны точкой, а с другой стороны - линией.

Можно также рассматривать раскраски плоскости, в которых наборы точек каждого цвета ограничены наборами определенного типа.^[8] Такие ограничения могут привести к увеличению необходимого количества цветов, поскольку они не позволяют считать определенные цвета приемлемыми. Например, если раскраска плоскости состоит из областей, ограниченных Кривые Иордании, то требуется не менее шести цветов.^[9]

Смотрите также

Теорема четырех цветов

Примечания

^ Сойфер (2008), стр. 557–563; Шела и Сойфер (2003).
^ Сойфер (2008), п. 19.
^ де Грей (2018).
^ Калаи (2018)
^ Ааронсон (2018)
^ Комментарий от Parts к Polymath Thread 16, 3 августа 2019 г.
^ Колсон (2002); Радойчич и Тот (2003).
^ См., Например, Крофт, сокольничий и парень (1991).
^ Вудол (1973); смотрите также Колсон (2004) для другого доказательства аналогичного результата.

внешняя ссылка

О'Рурк, Джозеф, «Проблема 57: Хроматическое число плоскости», Проект открытых проблем, заархивировано из оригинал на 2006-08-30
Мохар, Боян (2001), Хроматическое число диаграммы единичных расстояний
Калаи, Гил (2018), Задачи раскраски для расположений кругов (и псевдокружностей)
Грайм, Джеймс (27 февраля 2019 г.), «Красочная нерешенная проблема», Numberphile

[1] Сойфер (2008), стр. 557–563; Шела и Сойфер (2003).

[2] Сойфер (2008), п. 19.

[FOOTNOTEde_Grey2018-3] де Грей (2018).

[4] Калаи (2018)

[5] Ааронсон (2018)

[6] Комментарий от Parts к Polymath Thread 16, 3 августа 2019 г.

[7] Колсон (2002); Радойчич и Тот (2003).

[8] См., Например, Крофт, сокольничий и парень (1991).

[9] Вудол (1973); смотрите также Колсон (2004) для другого доказательства аналогичного результата.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]