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

Математическая задача

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

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

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

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

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

Вариации

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

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

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

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

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

Примечания

1. Сойфер (2008), стр. 557–563; Шела и Сойфер (2003).
2. Бекман и Куорлз (1953).
3. Рассиас (2001).
4. Сойфер (2008), с. 19.
5. де Грей (2018).
6. Калай (2018); Ааронсон (2018)
7. Миксон (2021).
8. Коулсон (2002); Радойчич и Тот (2003).
9. Франкл и Уилсон (1981).
10. См., например, Croft, Falconer & Guy (1991).
11. Вудалл (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. Комбинировать. Прил. , 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, doi : 10.1038/scientificamerican1060-218 (неактивно 6 мая 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), «Überdeckung des euklidischen Raumes durch congruente Mengen», Португалия. Математика. , 4 : 238–242
• Хадвигер, Хьюго (1961), «Ungelöste Issuee No. 40», Elem. Математика. , 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, номер документа : 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 г.