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

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

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

(еще нерешенные задачи по математике)

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

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

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

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

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

История

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

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

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

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

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

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

Вариации

Эту задачу можно легко распространить на более высокие измерения. Нахождение хроматического числа трехмерного пространства представляет собой особенно интересную задачу. Как и в случае с версией в самолете, ответ неизвестен, но было показано, что это минимум 6 и максимум 15.

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

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

См. также

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

Ссылки

• Ааронсон, Скотт (11 апреля 2018 г.), Удивительный прогресс в решении давних открытых проблем
• Бекман, Ф.С.; Куорлз, Д.А. младший (1953), «Об изометриях евклидовых пространств», Труды Американского математического общества , 4 (5): 810–815, doi : 10.2307/2032415 , JSTOR   2032415 , MR   0058193
• де Брёйн, Нью-Йорк ; Эрдеш, П. (1951), «Проблема цвета бесконечных графов и проблема теории отношений» , Недерл. Акад. Ветенш. Учеб. Сер. А , 54 : 371–373, CiteSeerX   10.1.1.210.6623 , doi : 10.1016/S1385-7258(51)50053-7
• Чилакамарри, КБ (1993), «Проблема графа единичных расстояний: краткий обзор и некоторые новые результаты», Bull Inst. Комбинировать. Прил. , 8 : 39–60
• Чилакамарри, Киран Б.; Махони, Кэролайн Р. (1996), «Графы единичных расстояний, графики на целочисленной решетке и результат типа Рамсея», Aequationes Mathematicae , 51 (1–2): 48–67, doi : 10.1007/BF01831139 , MR   1372782 , S2CID   189831504
• Коулсон, Д. (2004). «О хроматическом числе плоских мозаик» . Журнал Австралийского математического общества . 77 (2). Издательство Кембриджского университета (CUP): 191–196. дои : 10.1017/s1446788700013574 . ISSN   1446-7887 .
• Коулсон, Д. (2002), «15-раскраска трехмерного пространства без учета первого расстояния», Discrete Math. , 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 г.), «Новый сборник головоломок» , Mathematical Games, Scientific American , 203 (4): 180, номер документа : 10.1038/scientificamerican1060-218 (неактивен 06 мая 2024 г.), JSTOR   24940666 {{citation}}: CS1 maint: DOI неактивен по состоянию на май 2024 г. ( ссылка ) CS1 maint: дата и год ( ссылка )
• де Грей, Обри DNJ (2018), «Хроматическое число плоскости не менее 5», Geombinatorics , 28 : 5–18, arXiv : 1804.02385 , Bibcode : 2016arXiv160407134W , MR   3820926
• Хадвигер, Хьюго (1945), «Покрытие евклидова пространства конгруэнтными множествами», Португалия. Математика , 4 : 238–242.
• Хадвигер, Хьюго (1961), «Нерешенные проблемы № 40», Элем. Математика , 16 : 103–104.
• Хойле, Марин Дж. Х. (2018), Вычисление малых графов единичных расстояний с хроматическим числом 5 , arXiv : 1805.12181 , Bibcode : 2018arXiv180512181H
• Дженсен, Томми Р.; Тофт, Бьерн (1995), Проблемы раскраски графов , Серия Wiley-Interscience по дискретной математике и оптимизации, стр. 150–152, ISBN  978-0-471-02865-9
• Калаи, Гил (10 апреля 2018 г.), Обри де Грей: Хроматическое число плоскости не менее 5.
• Миксон, Дастин (1 февраля 2021 г.), Polymath16, семнадцатая тема: Объявление о победе , получено 16 августа 2021 г.
• Polymath, DHJ (апрель 2018 г.), Задача Хадвигера-Нельсона (страница проекта Polymath) , заархивировано из оригинала 16 февраля 2022 г.
• Радойчич, Радош; Тот, Геза (2003), «Заметки о хроматическом числе пространства», Аронов, Борис; Басу, Саугата; Пах, Янош; Шарир, Миха (ред.), Дискретная и вычислительная геометрия: Festschrift Гудмана – Поллака (PDF) , Алгоритмы и комбинаторика, том. 25, Берлин: Springer, стр. 695–698, номер документа : 10.1007/978-3-642-55566-4_32 , ISBN.  978-3-540-00371-7 , МР   2038498
• Рассиас, Фемистокл М. (2001), «Изометрические отображения и проблема А. Д. Александрова для консервативных расстояний», Флориан, Х.; Ортнер, Н.; Шнитцер, Ф.Дж.; Тутшке В. (ред.), Функционально-аналитические и комплексные методы, их взаимодействие и приложения к уравнениям в частных производных: материалы международного семинара, состоявшегося в Технологическом университете Граца, Грац, 12–16 февраля 2001 г. , River Edge, Нью-Джерси: 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
• Вудалл, Д.Р. (1973), «Расстояния, реализуемые множествами, покрывающими плоскость», Журнал комбинаторной теории , серия A, 14 (2): 187–200, doi : 10.1016/0097-3165(73)90020-4 , MR   0310770

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

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