WikiDer > Гипотеза Хедетниемиса - Википедия

Hedetniemis conjecture - Wikipedia
Пример Гипотеза Хедетниеми: тензорное произведение C5 и C3 (слева) дает граф, содержащий цикл длиной 15 (справа), поэтому: итоговый граф требует 3 цветов.

В теория графов, Гипотеза Хедетниеми, сформулированный Стивен Т. Хедетниеми в 1966 году касается связи между раскраска графика и тензорное произведение графов. Эта гипотеза утверждает, что

Здесь обозначает хроматическое число неориентированного конечного графа .

Неравенство χ (грамм × ЧАС) ≤ min {χ (грамм), χ (ЧАС)} легко: если грамм является k-цветная, можно k-цвет грамм × ЧАС используя одну и ту же окраску для каждой копии грамм в продукте; симметрично, если ЧАС является k-цветный. Таким образом, гипотеза Хедетниеми сводится к утверждению, что тензорные произведения нельзя раскрасить в неожиданно малое количество цветов.

Контрпример к гипотезе открыл Ярослав Шитов (2019) (видеть Калаи 2019), тем самым опровергая гипотезу в целом.

Известные случаи

Для любого графа с непустым множеством ребер требуется как минимум два цвета; если грамм и ЧАС не 1-раскрашиваемы, то есть они оба содержат ребро, то их произведение также содержит ребро и, следовательно, тоже не 1-раскрашиваемо. В частности, гипотеза верна, когда грамм или же ЧАС является двудольным графом, так как тогда его хроматическое число равно 1 или 2.

Аналогично, если два графика грамм и ЧАС не являются двухцветными, то есть не двудольный, то оба содержат цикл нечетной длины. Поскольку произведение двух нечетных графики цикла содержит нечетный цикл, продукт грамм × ЧАС тоже не двухцветный. Другими словами, если грамм × ЧАС 2-раскрашиваем, то хотя бы один из грамм и ЧАС также должны быть двухцветными.

Следующий случай был доказан спустя много времени после утверждения гипотезы. Эль-Захар и Зауэр (1985): если продукт грамм × ЧАС 3-раскрашиваем, то один из грамм или же ЧАС также должен быть трехцветным. В частности, гипотеза верна всякий раз, когда грамм или же ЧАС 4-раскрашиваем (так как тогда неравенство χ (грамм × ЧАС) ≤ min {χ (грамм), χ (ЧАС)} может быть строгим только тогда, когда грамм × ЧАС В остальных случаях оба графика в тензорном произведении являются как минимум 5-хроматическими, и прогресс был достигнут только для очень ограниченных ситуаций.

Слабая гипотеза Хедетниеми

Следующая функция (известная как Функция Поляка-Рёдля) измеряет, насколько низкое хроматическое число продуктов п-хроматические графики могут быть.

Гипотеза Хедетниеми тогда эквивалентна утверждению, что ж(п) = п. Слабая гипотеза Хедетниеми вместо этого просто заявляет, что функция ж(пДругими словами, если тензорное произведение двух графов можно раскрасить в несколько цветов, это должно означать некоторое ограничение на хроматическое число одного из факторов.

Основной результат (Поляк и Рёдль 1981), независимо улучшенный Поляком, Джеймсом Х. Шмерлом и Чжу, утверждает, что если функция ж(п) ограничен, то он ограничен не более чем 9. Таким образом, доказательство гипотезы Хедетниеми для 10-хроматических графов уже влечет за собой слабую гипотезу Хедетниеми для всех графов.

Мультипликативные графы

Гипотеза изучается в более общем контексте гомоморфизмы графов, особенно из-за интересного отношения к категория графов (с графами как объектами и гомоморфизмами как стрелками). Для любого фиксированного графика K, рассматриваются графы грамм допускающие гомоморфизм K, написано граммK. Их также называют K-раскрашиваемые графики. Это обобщает обычное понятие раскраски графа, поскольку из определений следует, что a kраскраска такая же, как Kk-раскраска (гомоморфизм в полный граф на k вершины).

График K называется мультипликативный если для любых графиков грамм, ЧАС, дело в том, что грамм × ЧАСK следует, что граммK или же ЧАСK Как и в случае с классическими раскрасками, всегда имеет место обратная импликация: если грамм (или же ЧАС, симметрично) Kраскрашиваемый, то грамм × ЧАС легко K-крашивается с использованием тех же значений независимо от ЧАСГипотеза Хедетниеми тогда эквивалентна утверждению, что каждый полный граф мультипликативен.

Вышеуказанные известные случаи эквивалентны утверждению, что K1, K2, и K3 мультипликативны. K4 широко открыта. С другой стороны, доказательство Эль-Захар и Зауэр (1985) был обобщен Häggkvist et al. (1988) чтобы показать, что все графы циклов мультипликативны. Тардиф (2005) в более общем плане доказал, что все круговые клики Kн / к с п / к <4 мультипликативны. круговое хроматическое число χc, это означает, что если χc(грамм×ЧАС) < 4, тогда χc(грамм×ЧАС) = min { χc(грамм), χc(грамм)} . Врохна (2017) показал, что графы без квадратов мультипликативны.

Примеры не мультипликативных графов могут быть построены из двух графов грамм и ЧАС несравнимые в порядке гомоморфизма (т. е. ни граммЧАС ни ЧАСграмм держит). В этом случае, позволяя K=грамм×ЧАС, мы тривиально имеем грамм×ЧАСK, но ни грамм ни ЧАС может допускать гомоморфизм в K, поскольку составлен с проекцией KЧАС или же Kграмм это привело бы к противоречию.

Экспоненциальный график

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

f (v) примыкает к г (v ') в K, для всех смежных вершин v,v ' из грамм.

В частности, есть цикл у функции ж (она смежна сама с собой) тогда и только тогда, когда функция дает гомоморфизм из грамм к K. По-другому, есть грань между ж и грамм всякий раз, когда две функции определяют гомоморфизм из грамм × K2двусторонняя двойная обложка из грамм) к K.

Экспоненциальный график - это экспоненциальный объект в категории графиков. Это означает гомоморфизмы из грамм × ЧАС к графику K соответствуют гомоморфизмы из ЧАС к Kграмм. Более того, существует гомоморфизм eval: грамм × KграммK данный eval (v,ж) = ж(v)Эти свойства позволяют заключить, что мультипликативность K эквивалентно (Эль-Захар и Зауэр 1985) к заявлению:

либо грамм или же Kграмм является K-раскрашиваемый, для каждого графика грамм.

Другими словами, гипотезу Хедетниеми можно рассматривать как утверждение об экспоненциальных графах: для каждого целого числа k, график Kkграмм либо kраскрашиваемый, или он содержит цикл (что означает грамм является k-раскрашиваемый). Также можно увидеть гомоморфизмы eval: грамм × KkграммKk как тяжелейший примеры гипотезы Хедетниеми: если продукт грамм × ЧАС был контрпримером, тогда грамм × Kkграмм тоже был бы контрпримером.

Обобщения

Обобщенная на ориентированные графы, эта гипотеза имеет простые контрпримеры, как заметил Поляк и Рёдль (1981). Здесь хроматическое число ориентированного графа - это просто хроматическое число нижележащего графа, но тензорное произведение имеет ровно половину числа ребер (для ориентированных ребер g → g ' в грамм и ч → ч ' в ЧАС, тензорное произведение грамм × ЧАС имеет только одно ребро, от (г, ч) к (г ', ч'), в то время как продукт нижележащих неориентированных графов будет иметь ребро между (г, ч ') и (г ', ч) также). Однако гипотеза Слабого Хедетниеми оказывается эквивалентной в направленной и ненаправленной постановке (Тардиф и Веллау 2006).

Проблема не может быть обобщена на бесконечные графы: Хайнал (1985) привел пример двух бесконечных графов, каждый из которых требует бесчисленного количества цветов, так что их продукт может быть раскрашен только счетным количеством цветов. Ринот (2013) доказал, что в конструируемая вселенная, для каждого бесконечного кардинала , существует пара графов с хроматическим числом больше , так что их продукт можно раскрасить только счетным количеством цветов.

Связанные проблемы

Аналогичное равенство для декартово произведение графиков было доказано Сабидусси (1957) и впоследствии несколько раз открывали заново. Также известна точная формула лексикографическое произведение графов.Даффус, пески и Вудро (1985) представил две более сильные гипотезы об уникальной раскрашиваемости.

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

Основные источники
  • Даффус, Д.; Пески, В .; Вудро, Р. Э. (1985), "О хроматическом числе произведения графов", Журнал теории графов, 9 (4): 487–495, Дои:10.1002 / jgt.3190090409, МИСТЕР 0890239.
  • Эль-Захар, М .; Зауэр, Н. (1985), "Хроматическое число произведения двух 4-хроматических графов равно 4", Комбинаторика, 5 (2): 121–126, Дои:10.1007 / BF02579374, МИСТЕР 0815577.
  • Häggkvist, R .; Черт, П.; Миллер, Д. Дж .; Нойман Лара, В. (1988), "О мультипликативных графах и гипотезе произведения", Комбинаторика, 8 (1): 63–74, Дои:10.1007 / BF02122553, HDL:1828/1589, МИСТЕР 0951994.
  • Хайнал, А. (1985), «Хроматическое число произведения двух ℵ1 хроматические графы можно исчислить », Комбинаторика, 5 (2): 137–140, Дои:10.1007 / BF02579376, МИСТЕР 0815579.
  • Хедетниеми, С. (1966), Гомоморфизмы графов и автоматов, Технический отчет 03105-44-T, Мичиганский университет.
  • Поляк, С .; Рёдль, В. (1981), «О дуго-хроматическом числе орграфа», Журнал комбинаторной теории, серия B, 31 (2): 190–198, Дои:10.1016 / S0095-8956 (81) 80024-X.
  • Ринот, А. (2013), Гипотеза Хедетниеми для несчетных графов, arXiv:1307.6841, Bibcode:2013arXiv1307.6841R.
  • Сабидусси, Г. (1957), «Графы с заданной группой и заданными теоретико-графовыми свойствами», Канадский математический журнал, 9: 515–525, Дои:10.4153 / CJM-1957-060-7, МИСТЕР 0094810.
  • Шитов, Ярослав (май 2019), Контрпримеры к гипотезе Хедетниеми, arXiv:1905.02167.
  • Тардиф, К. (2005), "Мультипликативные графы и полурешеточные эндоморфизмы в категории графов", Журнал комбинаторной теории, серия B, 95 (2): 338–345, Дои:10.1016 / j.jctb.2005.06.002.
  • Тардиф, С .; Wehlau, D. (2006), "Хроматические числа произведений графов: направленные и неориентированные версии функции Поляка-Рёдля", Журнал теории графов, 51 (1): 33–36, Дои:10.1002 / jgt.20117.
  • Врохна, М. (2017), «Графы без квадратов мультипликативны», Журнал комбинаторной теории, серия B, 122: 479–507, arXiv:1601.04551, Дои:10.1016 / j.jctb.2016.07.007.
Обзоры и вторичные источники

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