Гипотезы, подразумевающие теорему о четырех цветах

38

Теорема о четырех цветах (4CT) гласит, что каждый планарный граф имеет четыре раскраски. Есть два доказательства, представленные [Аппель, Хакен 1976] и [Робертсон, Сандерс, Сеймур, Томас 1997]. Оба эти доказательства являются компьютерными и довольно пугающими.

Есть несколько гипотез в теории графов, которые подразумевают 4CT. Разрешение этих предположений, вероятно, требует лучшего понимания доказательств 4CT. Вот одна из таких гипотез:

Гипотеза : Пусть - плоский граф, пусть C - множество цветов, а f : C C - свободная инволюция с фиксированной точкой. Пусть L = ( L v : v V ( G ) ) таково, чтоGCf:CCL=(Lv:vV(G))

  • для всех v V и|Lv|4vV
  • если , то F ( & alpha ; ) L V для всех об V , для всех альфа C .αLvf(α)LvvVαC

Тогда существует -раскраска графа G .LG

Если вам известны такие предположения, подразумевающие 4CT, перечислите их по одному в каждом ответе. Я не смог найти исчерпывающий список таких догадок.

Шива Кинтали
источник
6
«У них не было ошибки в Coq, и никакие космические лучи не проходили через их компьютер, когда они проверяли теорему о 4 цветах» - одна из таких гипотез.
Андрей Бауэр
Ref для заявленной гипотезы?
vzn
Соответствующий вопрос задают на mathoverflow: mathoverflow.net/q/189097/1345
Ян Агол

Ответы:

28

4CT эквивалентно:

Александр бондаренко
источник
20

Другая механическая проверка теоремы о 4 цветах была сделана Джорджем Гонтье из Microsoft Research Cambridge. Разница с его доказательством состоит в том, что вся теорема была сформулирована и механически проверена с использованием помощника по доказательству Coq, в то время как другие доказательства содержат только вычисления ядра, написанные на ассемблере и C, и, таким образом, могут быть ошибочными. Доказательство Гонтье охватывает как вычислительные, так и логические аспекты всего в 60 000 строк Coq.

Дэйв Кларк
источник
19

Я говорил об этом в своем блоге, и наше понимание таково: например, состояние Тейта может быть ослаблено, так как существует раскраска, в которой не более o (n) ошибок. Смотрите здесь: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/

Дик Липтон
источник
1
Очень круто! Спасибо за эту переформулировку!
Сянь-Чжи Чанг 10 之
18

Посмотрите на Т. Саати, Тринадцать красочных вариаций четырехцветной гипотезы Гатри, Американская математика. Ежемесячно, 79 (1972) 2-43 для многих примеров.

Кроме того, в книге Дэвида Барнетта «Раскраска карты, многогранники и проблема четырех цветов», MAA, серия Dolciani, том 8, 1983, приводится много примеров. Один особенно интересный результат в книге Барнете таков: если всегда можно обрезать вершины выпуклого многогранника, чтобы получить трехвалентный выпуклый многогранник так, чтобы число сторон каждой грани было кратно трем, это подразумевает правда четырехцветной гипотезы.

Иосиф Малкевич
источник
12

В статье « Абсолютные плоские ретракты и четырехцветная гипотеза» Павол Ад доказал несколько эквивалентных формулировок для 4CT. Один из них гласит:

Каждый планарный граф 4-раскрашивается (4CT), если существует абсолютный плоский ретракт.

HGGr:V(G)V(H)r(v)=vvV(H)

Пэн О
источник
11

Каждый кубический плоский план без мостов имеет 3-краевое окрашивание. (Это эквивалентно 4CT, из-за Тейта.)

Эндрю Д. Кинг
источник
11

Статья Дрора Бар-Натана «Алгебры Ли и теорема о четырех цветах» (Combinatorica 17-1 (1997) 43-52, последнее обновление - октябрь 1999 г., arXiv: q-alg / 9606016 ) содержит привлекательное утверждение об алгебрах Ли, эквивалентное Теорема о четырех цветах. Понятия, фигурирующие в утверждении, появляются и в теории инвариантов конечного типа узлов (инвариантов Васильева) и 3-многообразий.

Гил Калай
источник
11

Предложение 2.4 в этом документе http://www.sciencedirect.com/science/article/pii/0012365X9500109A# дает другую формулировку для 4CT.

GΔ(G)GGΔ(G)GGΔ(G)Δ(G)


GK(G)GK(G)G
GK(G)

VB Le
источник
4
Можете ли вы описать это здесь для тех из нас, кто не имеет доступа (или, как я, слишком ленив, чтобы включить VPN для получения доступа)?
Дэвид Эппштейн
9

Описание высокого уровня автоматизированного доказательства, сделанное Гонтье, стоит прочитать, если вы ищете более глубокое понимание.

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

Андраш Саламон
источник
8

Я только что прочитал в статье Чалопина и Гонсалвеса (STOC '09) следующую гипотезу Запада:

Каждый планарный граф является графом пересечения отрезков на плоскости, используя только четыре направления.

Поскольку параллельные сегменты образуют независимое множество в таком представлении, эта гипотеза подразумевает 4CT, но, возможно, даже сильнее.

Ссылка: Запад, Открытые проблемы . SIAM J Discrete Math Newsletter, 2 (1): 10-12, 1991.

RJK
источник
6

Снарк является связным, bridgeless кубического графа , который не рёберный 3-раскраски. Следуя википедии, догадка о догадках , обобщающая 4CT, выглядит следующим образом:

У каждой snark есть подграф, который может быть сформирован из графа Петерсена путем деления некоторых его ребер.

Опять же, согласно википедии, доказательство этой гипотезы было объявлено в 2001 году Робертсоном, Сандерсом, Сеймуром и Томасом.

Герман Грубер
источник
Теорема Снарка, похоже, не подразумевает 4CT, верно?
Сянь-Чи Чанг 之 之
На самом деле это подразумевает 4CT: каждое подразделение графа Петерсена явно неплоское, поэтому гипотеза снарка подразумевает следующую переформулировку 4CT (из-за Тейта): каждая змея непланарна.
Герман Грубер
1
Ах, теперь я вижу, где моя проблема. Доказательство теоремы Снарка снова является компьютерным доказательством. У меня сложилось впечатление, что нет никаких проверяемых человеком доказательств 4СТ, и я неправильно понял ваш ответ. Благодарность!!
Сянь-Чи Чанг
3

«Маркировка лица максимальных плоских графов» - это название моей старой статьи, недавно опубликованной, в которой я преобразовал 4 раскраски максимальных плоских графов в последовательность маркировки граней. Ссылка на статью http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf

Cahit
источник
3

Как

Л. Х. Кауфман, Переформулировка теоремы о цвете отображения , Дискретная математика 302 (2005) 145–172

указывает на то, что принцип Примальности, обусловленный Г. Спенсером-Брауном, а также гипотеза Элиахо-Крючкова являются эквивалентными переформулировками ПКТ.

  • S. Eliahou, Подписанные диагональные сальто и теорема о четырех цветах, европейский J. Combin. 20 (1999) 641–646.
  • С. И. Крючков, Теорема о четырех цветах и ​​деревья, И. В. Кручатов, Институт атомной энергии, Москва, 1992, IAE-5537/1.
  • Г. Спенсер-Браун, Законы формы, Gesetze der Form, Bohmeier Verlag, 1997.
Герман Грубер
источник
3

Статья Гарри Боулина и Мэтью Дж. Брина «Раскраска плоских графиков с помощью цветных контуров в ассоциаэдрах», последняя редакция 12 мая 2013 года, arXiv: 1301.3984 math.CO, содержит следующую гипотезу на странице 26:

Гипотеза 6.4. Для каждой пары конечных двоичных деревьев (D, R) с одинаковым числом листьев существует присвоение знака D и правильное для D слово w символов вращения, так что Dw = R.

Утверждается, что гипотеза 6.4, вытекающая из предыдущих положений и теорем в статье, эквивалентна 4CT.

Дэвид Кларк
источник
1

К -потоку на неориентированном графе G представляет собой ориентированный граф , полученный путем замены каждого ребра в G с дугой и присвоением ему целое числа между -k и к , исключительным, таким , что для каждой вершины в G, сумма целых чисел назначенный дугам, указывающим на эту вершину, равен сумме целых чисел, назначенных дугам, указывающим. NWZ (нигде ноль) k- поток - это k- поток, в котором ни одной дуге не был присвоен номер 0.

Для любого плоского графа G двойство G - это граф, который содержит одну вершину для каждой грани в плоском вложении G , и две вершины в двойственном числе делят одно ребро, соединяя их для каждого ребра, которое соответствующие грани в G разделяют между ними в их границах. Согласно TUTTE в Flow-раскраска теорему двойственности, плоский граф, без перешейка (т.е. краев которого удаление приведет к увеличению числа компонентов) имеет NWZ к -потоку тогда и только тогда , когда его сопряженный к -colourable. Другими словами, планарный граф является 4-цветным тогда и только тогда, когда его двойственный имеет 4-поток NWZ.

Обратите внимание, что 4CT требует, чтобы у рассматриваемого плоского графа не было петель (ребер, соединяющих любую вершину с самим собой), потому что любой граф с петлей не может быть окрашен в вершины с любым набором цветов, поскольку любая вершина с петлей была бы смежной с вершины одного цвета, независимо от их цвета.

Джордан Лонгстафф
источник
0

Я работаю над этим:

Если вы можете доказать теорему для прямоугольных карт, которые являются картами, сделанными из перекрывающихся листов бумаги, вы также доказали 4ct. Кроме того, в поиске могут рассматриваться только карты с гранями, имеющими все 5 или более ребер.

Смотрите http://4coloring.wordpress.com/ для деталей.

Марио Стефанутти
источник