Шпиндель Мозера - Moser spindle

Шпиндель Мозера
Псевдотриангуляция шпинделя Мозера.svg
Названный в честьЛео Мозер, Уильям Мозер
Вершины7
Края11
Радиус2
Диаметр2
Обхват3
Автоморфизмы8
Хроматическое число4
Хроматический индекс4
Характеристикипланарный
единичное расстояние
Граф Ламана
Таблица графиков и параметров

В теория графов, раздел математики, Шпиндель Мозера (также называемый Шпиндель Мозера или же Граф Мозера) является неориентированный граф, названный в честь математиков Лео Мозер и его брат Уильям,[1] с семью вершинами и одиннадцатью ребрами. Это график единичного расстояния требуя четырех цветов в любом раскраска графика, и его существование может быть использовано для доказательства того, что хроматический номер плоскости не меньше четырех.[2]

Шпиндель Мозера также называют График Хайоша после Дьёрдь Хаджос, поскольку его можно рассматривать как экземпляр Строительство Hajós.[3] Однако название «граф Хайоша» применялось и к другому графу в форме треугольника, вписанного в шестиугольник.[4]

Строительство

Веретено Мозера, встроенное в плоскость в виде графика единичных расстояний, вместе с семицветной раскраской плоскости.

В качестве диаграммы единичных расстояний шпиндель Мозера состоит из двух ромбовидные с углами 60 и 120 градусов, так что стороны и короткие диагонали ромбов образуют равносторонние треугольники. Два ромба размещены в плоскости, разделяя одну из своих остроугольных вершин таким образом, что оставшиеся две остроугольные вершины находятся на расстоянии единицы друг от друга. Одиннадцать ребер графа - это восемь сторон ромба, две короткие диагонали ромбов и ребро между парой остроугольных вершин с единичным расстоянием.

Строительство Hajós шпинделя Мозера

Веретено Мозера также может быть построено теоретически графически, без ссылки на геометрическое вложение, с использованием Строительство Hajós начиная с двух полных графов на четырех вершинах. Эта конструкция удаляет ребро из каждого полного графа, объединяет две конечные точки удаленных ребер в одну вершину, разделяемую обеими кликами, и добавляет новое ребро, соединяющее оставшиеся две конечные точки удаленного ребра.[5]

Другой способ изготовления шпинделя Мозера - это как дополнительный граф графа, сформированного из график полезности K3,3 разделив одно из его ребер.[6]

Приложение к проблеме Хадвигера – Нельсона

В Проблема Хадвигера – Нельсона спрашивает, сколько цветов необходимо для раскраски точек евклидовой плоскости таким образом, чтобы каждой паре точек на единичном расстоянии друг от друга были назначены разные цвета. То есть он просит хроматическое число бесконечного графа, вершинами которого являются все точки на плоскости, а ребрами - все пары точек на единичном расстоянии.[2]

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

Альтернативное доказательство того, что веретено Мозера требует четырех цветов, следует из конструкции Хайоса. Оба полных графа, из которых формируется веретено Мозера, требуют четырех цветов, и конструкция Хажоса сохраняет это свойство.[5] Более того, каждый независимый набор в веретене Мозера не более двух вершин,[7] поэтому для покрытия всех семи вершин требуется по крайней мере четыре независимых набора.

Поскольку веретено Мозера является подграфом графа бесконечных единичных расстояний плоскости, граф плоскости также требует не менее четырех цветов в любой раскраске. Посредством Теорема де Брейна – Эрдеша (в предположении, что аксиома выбора верно), хроматическое число плоскости совпадает с наибольшим хроматическим числом любого из ее конечных подграфов; до открытия семейства 5-хроматических графов единичных расстояний в 2018 году не было обнаружено ни одного подграфа бесконечного графа единичных расстояний, который требует большего количества цветов, чем веретено Мозера. Однако наилучшая верхняя граница для хроматического числа плоскости - семь, что значительно превышает количество цветов, необходимое для веретена Мозера.[2]

Другие свойства и приложения

Шпиндель Мозера - это планарный граф, то есть его можно рисовать без пересечений на плоскости. Однако невозможно сформировать такой чертеж с прямыми краями, который также является чертежом с единичным расстоянием; то есть это не график спичек. Шпиндель Мозера также Граф Ламана, что означает, что он образует минимально жесткая система при врезании в самолет.[8] Как планарный граф Ламана, это граф точечной псевдотриангуляции, что означает, что он может быть вложен в плоскость таким образом, что неограниченная грань является выпуклый корпус вложения и каждая ограниченная грань является псевдотреугольник всего с тремя выпуклыми вершинами.[9]

В дополнительный граф графа Мозера является граф без треугольников. Таким образом, вложение в единичное расстояние графа Мозера можно использовать для решения проблемы размещения семи точек на плоскости таким образом, чтобы каждая тройка точек содержала по крайней мере одну пару на единичном расстоянии друг от друга.[2][10]

Добавление любого ребра к шпинделю Мозера приводит к тому, что граф не может быть встроен в плоскость как граф единичных расстояний, и не существует гомоморфизм графов от шпинделя Мозера к любому меньшему графику единичных расстояний. Эти два свойства шпинделя Мозера использовались Хорват, Краточвил и Писанский (2011) показать NP-твердость проверки того, имеет ли данный граф двумерное представление единичного расстояния; в доказательстве используется редукция от 3СБ в котором веретено Мозера используется как центральная установка истины гаджет в сокращении.[8]

Веретено Мозера также можно использовать для доказательства результата в евклидовом Теория Рамсея: если Т есть любой треугольник на плоскости, и точки на плоскости двухцветные: черный и белый, то есть либо черный перевод Т или пара белых точек на единичном расстоянии друг от друга. Ибо пусть M - вложение шпинделя Мозера на единичное расстояние, и пусть M + Т быть Сумма Минковского из M иТ. Если M + Т не имеет белой пары единиц измерения расстояния, то каждая из трех копий веретена Мозера в M + Т должно иметь не более двух белых точек, потому что белые точки в каждой копии должны образовывать независимый набор а самый большой независимый набор в шпинделе Moser имеет размер два. Следовательно, среди семи вершин веретена Мозера не более шести имеют белую копию в M + Т, поэтому должна быть одна из семи вершин, все копии которых черные. Но тогда три копии этой вершины образуют перевод Т.[7]

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

Рекомендации

  1. ^ Мозер, Л.; Мозер, В. (1961), «Решение проблемы 10», Может. Математика. Бык., 4: 187–189.
  2. ^ а б c d Сойфер, Александр (2008), Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей, Нью-Йорк: Springer, стр. 14–15, ISBN  978-0-387-74640-1.
  3. ^ Bondy, J. A .; Мурти, США (2008), Теория графов, Тексты для выпускников по математике, 244, Springer, стр. 358, Дои:10.1007/978-1-84628-970-5, ISBN  978-1-84628-969-9.
  4. ^ Берге, К. (1989), "Минимаксные соотношения для частичных q-раскраски графа », Дискретная математика, 74 (1–2): 3–14, Дои:10.1016 / 0012-365X (89) 90193-3, МИСТЕР  0989117.
  5. ^ а б Хайос, Г. (1961), "Über eine Konstruktion nicht" п-färbbarer Graphen ", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Рейхе, 10: 116–117.
  6. ^ Gervacio, Severino V .; Лим, Иветт Ф .; Маэхара, Хироши (2008), «Планарные графы единичных расстояний, имеющие плоское дополнение единичных расстояний», Дискретная математика, 308 (10): 1973–1984, Дои:10.1016 / j.disc.2007.04.050, МИСТЕР  2394465.
  7. ^ а б Беркерт, Джеффри; Джонсон, Питер (2011), «Лемма Шлама: мутантное потомство евклидовой проблемы Рамсея 1973 года с многочисленными приложениями», Теория Рамсея, Прогр. Математика, 285, Birkhäuser / Springer, Нью-Йорк, стр. 97–113, Дои:10.1007/978-0-8176-8092-3_6, МИСТЕР  2759046. Смотрите также Сойфер (2008), Задача 40.26, с. 496.
  8. ^ а б Хорват, Борис; Кратохвил, Ян; Писанский, Томаж (2011), "О вычислительной сложности вырожденных представлений графов на единичном расстоянии", Комбинаторные алгоритмы: 21-й международный семинар, IWOCA 2010, Лондон, Великобритания, 26-28 июля 2010 г., пересмотренные избранные статьи, Конспект лекций по информатике, 6460, стр. 274–285, arXiv:1001.0886, Bibcode:2011LNCS.6460..274H, Дои:10.1007/978-3-642-19222-7_28, ISBN  978-3-642-19221-0.
  9. ^ Хаас, Рут; Орден, Дэвид; Роте, Гюнтер; Сантос, Франциско; Серватиус, Бриджит; Серватий, Герман; Сувейн, Дайан; Стрейну, Илеана; Уайтли, Уолтер (2005), «Плоские минимально жесткие графы и псевдотриангуляции», Теория вычислительной геометрии и приложения, 31 (1–2): 31–61, arXiv:математика / 0307347, Дои:10.1016 / j.comgeo.2004.07.003, МИСТЕР  2131802.
  10. ^ Винклер, Питер (Ноябрь 2011 г.), «Озадаченные: расстояния между точками на плоскости», Коммуникации ACM, 54 (11): 120, Дои:10.1145/2018396.2018422. Решение, выпуск 12, декабрь 2011 г., Дои:10.1145/2043174.2043200.

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