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

Нерешенная задача по математике :

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

(еще нерешенные проблемы по математике)

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

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

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

Отношение к конечным графам

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

История

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

Одно из приложений проблемы связывает ее с теоремой Бекмана–Куорлза , согласно которой любое отображение евклидовой плоскости (или любого пространства большей размерности) на себя, сохраняющее единичные расстояния, должно быть изометрией , сохраняющей все расстояния. ^[2] Конечные раскраски этих пространств могут быть использованы для построения отображений из них в пространства большей размерности, которые сохраняют расстояния, но не являются изометриями. Например, евклидову плоскость можно отобразить в шестимерное пространство, раскрасив ее семью цветами так, чтобы никакие две точки на расстоянии один не имели одинакового цвета, а затем отобразив точки по их цветам в семь вершин шестимерного правильного симплекса с ребрами единичной длины. Это отображает любые две точки на единичном расстоянии в различные цвета, а оттуда в различные вершины симплекса, находящиеся на единичном расстоянии друг от друга. Однако это отображает все другие расстояния в ноль или единицу, поэтому это не изометрия. Если бы количество цветов, необходимых для окраски плоскости, можно было бы уменьшить с семи до меньшего числа, то такое же уменьшение было бы применено к размерности целевого пространства в этой конструкции. ^[3]

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

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

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

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

Вариации

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

В n -мерном случае задачи простая верхняя граница числа требуемых раскрасок, найденная из мозаики n -мерных кубов, равна . Нижняя граница из симплексов равна . Для нижняя граница доступна с использованием обобщения веретена Мозера: пары объектов (каждый из двух симплексов склеен на грани), которые соединены с одной стороны точкой, а с другой стороны линией. Экспоненциальная нижняя граница была доказана Франклом и Уилсоном в 1981 году. ^[9] $\lfloor 2+{\sqrt {n}}\rfloor ^{n}$ $n+1$ $n>1$ $n+2$

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

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

Теорема о четырех красках

Примечания

^ Сойфер (2008), стр. 557–563; Шела и Сойфер (2003).
^ Бекман и Куорлз (1953).
^ Рассиас (2001).
^ Сойфер (2008), стр. 19.
^ де Грей (2018).
^ Калай (2018); Ааронсон (2018)
^ Миксон (2021).
^ Коулсон (2002); Радойчич и Тот (2003).
^ Франкл и Уилсон (1981).
^ См., например, Крофт, Фалконер и Гай (1991).
^ Вудалл (1973); см. также Коулсон (2004) для другого доказательства аналогичного результата.

Ссылки

Ааронсон, Скотт (11 апреля 2018 г.), Удивительный прогресс в решении давних открытых проблем
Бекман, Ф. С.; Куорлз, Д. А. младший (1953), «Об изометриях евклидовых пространств», Труды Американского математического общества , 4 (5): 810–815, doi : 10.2307/2032415 , JSTOR 2032415, MR 0058193
де Брёйн, Нью-Йорк ; Эрдеш, П. (1951), «Проблема цвета бесконечных графов и проблема теории отношений», Nederl. Акад. Ветенш. Учеб. Сер. А , 54 : 371–373, CiteSeerX 10.1.1.210.6623 , doi : 10.1016/S1385-7258(51)50053-7
Чилакамарри, КБ (1993), «Проблема единичного расстояния в графе: краткий обзор и некоторые новые результаты», Bull Inst. Combin. Appl. , 8 : 39–60
Chilakamarri, Kiran B.; Mahoney, Carolyn R. (1996), «Графы единичных расстояний, графы на целочисленной решетке и результат типа Рамсея», Aequationes Mathematicae , 51 (1–2): 48–67, doi :10.1007/BF01831139, MR 1372782, S2CID 189831504
Коулсон, Д. (2004). «О хроматическом числе плоских мозаик». Журнал Австралийского математического общества . 77 (2). Cambridge University Press (CUP): 191–196. doi : 10.1017/s1446788700013574 . ISSN 1446-7887.
Коулсон, Д. (2002), «15-цветная раскраска 3-мерного пространства с исключением расстояния один», Дискретная математика , 256 (1–2): 83–90, doi :10.1016/S0012-365X(01)00183-2
Крофт, Халлард Т.; Фалконер, Кеннет Дж .; Гай, Ричард К. (1991), Нерешенные задачи по геометрии , Springer-Verlag, Задача G10, ISBN 978-0-387-97506-1
Франкл, П.; Уилсон, Р. М. (1981), «Теоремы пересечения с геометрическими следствиями», Combinatorica , 1 (4): 357–368, doi :10.1007/BF02579457, S2CID 6768348
Гарднер, Мартин (октябрь 1960 г.), «Новая коллекция «головоломок»", Математические игры, Scientific American , 203 (4): 180, doi : 10.1038/scientificamerican1060-218 (неактивен 2024-05-06), JSTOR 24940666{{citation}}: CS1 maint: DOI неактивен по состоянию на май 2024 г. ( ссылка ) CS1 maint: дата и год ( ссылка )
de Grey, Aubrey DNJ (2018), «Хроматическое число плоскости не менее 5», Geombinatorics , 28 : 5–18, arXiv : 1804.02385 , Bibcode : 2016arXiv160407134W, MR 3820926
Хадвигер, Хьюго (1945), «Überdeckung des euklidischen Raumes durch kongruente Mengen», Португалия. Математика. , 4 : 238–242
Хадвигер, Хьюго (1961), «Ungelöste Issuee No. 40», Elem. Математика. , 16 : 103–104
Heule, Marijn JH (2018), Вычисление небольших графов единичных расстояний с хроматическим числом 5 , arXiv : 1805.12181 , Bibcode : 2018arXiv180512181H
Дженсен, Томми Р.; Тофт, Бьярне (1995), Проблемы раскраски графов , Wiley-Interscience Series in Discrete Mathematics and Optimization, стр. 150–152, ISBN 978-0-471-02865-9
Калай, Джил (10 апреля 2018 г.), Обри де Грей: Хроматическое число плоскости не менее 5
Миксон, Дастин (1 февраля 2021 г.), Polymath16, семнадцатая тема: Declaring victory , получено 16 августа 2021 г.
Polymath, DHJ (апрель 2018 г.), задача Хадвигера-Нельсона (страница проекта Polymath), заархивировано из оригинала 2022-02-16
Radoičić, Radoš; Tóth, Géza (2003), «Заметка о хроматическом числе пространства», в Aronov, Борис; Basu, Saugata; Pach, Janos; Sharir, Micha (ред.), Discrete and Computational Geometry: The Goodman–Pollack Festschrift (PDF) , Алгоритмы и комбинаторика, т. 25, Берлин: Springer, стр. 695–698, doi :10.1007/978-3-642-55566-4_32, ISBN 978-3-540-00371-7, МР 2038498
Рассиас, Фемистокл М. (2001), «Изометрические отображения и проблема А. Д. Александрова для консервативных расстояний», в Florian, H.; Ortner, N.; Schnitzer, FJ; Tutschke, W. (ред.), Функционально-аналитические и комплексные методы, их взаимодействие и применение к уравнениям с частными производными: Труды международного семинара, проведенного в Технологическом университете Граца, Грац, 12–16 февраля 2001 г. , River Edge, New Jersey: World Scientific Publishing Co., Inc., стр. 118–125, doi : 10.1142/4822, ISBN 978-981-02-4764-5, г-н 1893253
Шелах, Сахарон ; Сойфер, Александр (2003), «Аксиома выбора и хроматическое число плоскости», Журнал комбинаторной теории, Серия A , 103 (2): 387–391, doi :10.1016/S0097-3165(03)00102-X
Сойфер, Александр (2008), Математическая раскраска: математика раскрашивания и красочная жизнь ее создателей , Нью-Йорк: Springer, ISBN 978-0-387-74640-1
Вудолл, DR (1973), «Расстояния, реализуемые множествами, покрывающими плоскость», Журнал комбинаторной теории , Серия A, 14 (2): 187–200, doi : 10.1016/0097-3165(73)90020-4 , MR 0310770

Внешние ссылки

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