Сколько цветов нужно, чтобы раскрасить плоскость, чтобы никакие две точки на единичном расстоянии не были одного цвета?
В геометрической теории графов , то Хадвигера-Нельсон , названный в честь Уго Хадвигеру и Эдвард Нельсон , просит минимальное количество цветов , необходимых для окрашивания плоскости такое , что никакие две точки на расстоянии 1 друг от друга не имеют такой же цвет. Ответ неизвестен, но был сужен до одного из чисел 5, 6 или 7. Правильное значение может зависеть от выбора аксиом для теории множеств . [1]
Связь с конечными графами
В терминах теории графов вопрос можно сформулировать следующим образом. Пусть G - граф единичных расстояний на плоскости: бесконечный граф со всеми точками плоскости в качестве вершин и с ребром между двумя вершинами тогда и только тогда, когда расстояние между двумя точками равно 1. Задача Хадвигера – Нельсона состоит в том, чтобы найти хроматическое число из G . Как следствие, проблему часто называют «нахождение хроматического числа плоскости». По теореме де Брюйна – Эрдеша , результату де Брюйна и Эрдеша (1951) , задача эквивалентна (в предположении выбранной аксиомы ) задаче нахождения максимально возможного хроматического числа конечного единичного графа расстояний.
История
Согласно Дженсену и Тофту (1995) , проблема была впервые сформулирована Нельсоном в 1950 году и впервые опубликована Гарднером (1960) . Хадвигер (1945) ранее опубликовал связанный результат, показывающий, что любое покрытие плоскости пятью конгруэнтными замкнутыми множествами содержит единичное расстояние в одном из множеств, и он также упомянул эту проблему в более поздней статье ( Hadwiger 1961 ). Сойфер (2008) подробно обсуждает проблему и ее историю.
Нижняя и верхняя границы
Тот факт, что хроматическое число плоскости должно быть не менее четырех, следует из существования единичного графа расстояний с семью вершинами с хроматическим числом четыре, названного веретеном Мозера после его открытия в 1961 году братьями Уильямом и Лео Мозер . Этот граф состоит из двух равносторонних равносторонних треугольников, соединенных в общей вершине x . Каждый из этих треугольников соединен по другому ребру с другим равносторонним треугольником; вершины y и z этих соединенных треугольников находятся на единичном расстоянии друг от друга. Если бы плоскость могла быть трехцветной, раскраска внутри треугольников заставила бы y и z иметь тот же цвет, что и x , но тогда, поскольку y и z находятся на единичном расстоянии друг от друга, у нас не было бы правильной раскраски графа единичных расстояний до плоскости. Следовательно, необходимо как минимум четыре цвета, чтобы раскрасить этот граф и содержащую его плоскость. Альтернативная нижняя граница в виде четыреххроматического графа расстояний с десятью вершинами, граф Голомба , была обнаружена примерно в то же время Соломоном В. Голомбом . [2]
В 2018 году компьютерный ученый и биолог Обри де Грей обнаружил не-4-раскрашиваемый граф единичных расстояний с 1581 вершиной. Доказательство - компьютерная помощь. [3] Математик Гил Калаи [4] и ученый-компьютерщик Скотт Ааронсон [5] опубликовали обсуждение открытия де Грея, при этом Ааронсон сообщил о независимых проверках результата де Грея с использованием решателей SAT . Калаи связал дополнительные сообщения Джордана Элленберга и Ноама Элкиса с Элкисом и (отдельно) де Греем, предлагающими проект Polymath по поиску не 4-раскрашиваемых графов единичных расстояний с меньшим количеством вершин, чем в конструкции де Грея. По состоянию на 2018 год самый маленький из известных графов с хроматическим числом 5 имел 553 вершины Heule (2018) , но в августе 2019 года Яан Партс нашел пример с 510 вершинами. [6] Страница проекта Polymath, Polymath (2018) , содержит дальнейшие исследования, ссылки в СМИ и данные проверки.
Верхняя граница семи для хроматического числа следует из существования мозаики плоскости правильными шестиугольниками с диаметром чуть меньше единицы, которым можно присвоить семь цветов в повторяющемся узоре, чтобы сформировать 7-цветную раскраску плоскости. Согласно Сойферу (2008) , эта верхняя граница впервые была обнаружена Джоном Р. Исбеллом .
Вариации
Проблема может быть легко расширена на более высокие измерения. В частности, определение хроматического числа пространства обычно относится к трехмерной версии. Как и в случае с версией в самолете, ответ неизвестен, но было показано, что оно должно быть от 6 до 15 [7].
В n -мерном случае задачи простая верхняя оценка количества требуемых раскрасок, найденных из мозаики n- мерных кубов, есть. Нижняя граница из симплексов равна. Для, нижняя граница доступен с использованием обобщения веретена Мозера: пара объектов (каждые 2 симплекса, склеенных вместе на фасете), которые соединены с одной стороны точкой, а с другой стороны - линией.
Можно также рассматривать раскраски плоскости, в которых наборы точек каждого цвета ограничены наборами определенного типа. [8] Такие ограничения могут привести к увеличению необходимого количества цветов, поскольку они не позволяют считать определенные цвета приемлемыми. Например, если раскраска плоскости состоит из областей, ограниченных жордановыми кривыми , то требуется не менее шести цветов. [9]
Смотрите также
- Теорема четырех цветов
Заметки
- ^ Сойфер (2008) , стр 557-563. Шела и Сойфер (2003) .
- ^ Сойфер (2008) , стр. 19.
- ^ де Грей (2018) .
- ^ Kalai (2018) ошибка harvtxt: несколько целей (2 ×): CITEREFKalai2018 ( справка )
- ^ Ааронсон (2018)
- ↑ Комментарий от Parts к теме Polymath Thread 16 , 3 августа 2019 г.
- ^ Колсон (2002) ; Радойчич и Тот (2003) .
- ^ См., Например, Croft, Falconer & Guy (1991) .
- ^ Вудалл (1973) ; см. также Coulson (2004) для другого доказательства аналогичного результата.
Рекомендации
- Ааронсон, Скотт (11 апреля 2018 г.), Удивительный прогресс в решении давних открытых проблем
- de Bruijn, NG ; Эрдеш, П. (1951), "Проблема цвета для бесконечных графов и проблема теории отношений" , Nederl. Акад. Wetensch. Proc. Сер. , 54 : 371-373, DOI : 10.1016 / S1385-7258 (51) 50053-7.
- Chilakamarri, KB (1993), "Проблема графа с единичным расстоянием: краткий обзор и некоторые новые результаты", Bull Inst. Комбинировать. Прил. , 8 : 39–60.
- Chilakamarri, Kiran B .; Махони, Каролин Р. (1996), "Единица расстояния графики, графики на целочисленной решетке и в результате типа Ramsey", Aequationes Mathematicae , 51 (1-2): 48-67, DOI : 10.1007 / BF01831139 , МР 1372782.
- Коулсон, Д. (2004), "О хроматическом числе плоских мозаик" , J. Austral. Математика. Soc. , 77 (2): 191–196, DOI : 10.1017 / S1446788700013574.
- Коулсон, Д. (2002), "15-раскраска 3-пространства без расстояния один", Discrete Math. , 256 (1-2): 83–90, DOI : 10.1016 / S0012-365X (01) 00183-2.
- Croft, Hallard T .; Falconer, Kenneth J .; Гай, Ричард К. (1991), Нерешенные проблемы геометрии , Springer-Verlag, Проблема G10.
- Гарднер, Мартин (1960), «Математические игры», Scientific American , 203/4: 180.
- де Грей, Обри DNJ (2018), «Хроматическое число плоскости не менее 5», Geombinatorics , 28 : 5–18, arXiv : 1804.02385 , Bibcode : 2016arXiv160407134W.
- Хадвигер, Хьюго (1945), "Überdeckung des euklidischen Raumes durch kongruente Mengen", Португалия. Математика. , 4 : 238–242.
- Хадвигер, Хьюго (1961), «Ungelöste Probleme No. 40», Elem. Математика. , 16 : 103–104.
- Heule, Marijn JH (2018), Вычисление малых графов единичных расстояний с хроматическим числом 5 , arXiv : 1805.12181 , Bibcode : 2018arXiv180512181H
- Дженсен, Томми Р .; Тофт, Бьярн (1995), Проблемы раскраски графов , Серия Wiley-Interscience по дискретной математике и оптимизации, стр. 150–152..
- Калаи, Гил (10 апреля 2018 г.), Обри де Грей: Хроматическое число плоскости не менее 5.
- Polymath, DHJ (апрель 2018 г.), проблема Хадвигера-Нельсона (страница проекта Polymath)CS1 maint: ref дублирует значение по умолчанию ( ссылка )
- Радойчич, Радош; Тот, Геза (2003), «Замечание о хроматическом числе пространства», Дискретная и вычислительная геометрия: Festschrift Гудмана – Поллака (PDF) , Алгоритмы и комбинаторика, 25 , Берлин: Springer, стр. 695–698, doi : 10.1007 / 978-3-642-55566-4_32 , MR 2038498.
- Шела, Сахарон ; Сойфер, Александр (2003), "Аксиома выбора и хроматического числа плоскости" (PDF) , Журнал комбинаторной теории, серия А , 103 (2): 387-391, DOI : 10.1016 / S0097-3165 (03) 00102 -X , заархивировано из оригинального (PDF) на 2011-06-14.
- Сойфер, Александр (2008), Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей , Нью-Йорк: Спрингер, ISBN 978-0-387-74640-1
- Woodall, DR (1973), «Расстояния, реализуемые множествами, покрывающими плоскость», Журнал комбинаторной теории , серия A, 14 (2): 187–200, DOI : 10.1016 / 0097-3165 (73) 90020-4 , MR 0310770
Внешние ссылки
- О'Рурк, Джозеф , «Проблема 57: Хроматическое число плоскости» , проект «Открытые задачи» , заархивировано из оригинала 30 августа 2006 г.
- Мохар, Боян (2001), Хроматическое число графа единичных расстояний
- Калаи, Гил (2018), Задачи раскраски для расположения кругов (и псевдокружностей)
- Грайм, Джеймс (27 февраля 2019 г.), «Красочная нерешенная проблема» , Numberphile