Гипотеза Хедетниеми

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

\chi (G\times H)=\min\{\chi (G),\chi (H)\}.

Здесь $\chi (G)$ обозначает хроматическое число неориентированного конечного графа $G$ .

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

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

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

Любой граф с непустым набором ребер требует как минимум двух цветов; если G и H не раскрашиваются в 1 цвет, то есть оба содержат ребро, то их произведение также содержит ребро и, следовательно, также не раскрашивается в 1 цвет. В частности, гипотеза верна, когда G или H — двудольный граф, поскольку тогда его хроматическое число равно либо 1, либо 2.

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

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

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

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

f(n)=\min\{\chi (G\times H)\colon \chi (G)=\chi (H)=n\}

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

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

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

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

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

Известные выше случаи эквивалентны утверждению, что K ₁ , K ₂ и K ₃ мультипликативны. Дело К ₄ широко раскрыто. С другой стороны, доказательство Эль-Захара и Зауэра (1985) было обобщено Хэггквистом и др. (1988), чтобы показать, что все графы циклов мультипликативны. Позже Тардиф (2005) доказал в более общем плане, что все круговые клики K _n/k с n/k < 4 мультипликативны. В терминах кругового хроматического числа χ _c это означает, что если $χ c (G \times H) < 4$ , то $χ c (G \times H) = min {χ c (G), χ c (G)}$ . Врочна (2017) показала, что графы без квадратов мультипликативны.

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

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

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

f(v) смежна с g(v') в K для всех смежных вершин v , v графа G. '

существует петля В частности, в функции f (она смежна сама с собой) тогда и только тогда, когда функция дает гомоморфизм из G в K . существует ребро С другой стороны, между f и g , когда две функции определяют гомоморфизм из G × K ₂ ( двудольное двойное накрытие G ) в K .

Экспоненциальный график — это экспоненциальный объект в категории графов. Это означает, что гомоморфизмам из G × H в граф K соответствуют гомоморфизмы из H в K. ^Г. Более того, существует гомоморфизм $eval : G \times K Г \to K$ , заданный $eval(v, f) знак равно ж (v)$ . Эти свойства позволяют заключить, что мультипликативность K эквивалентна ( Эль-Захар и Зауэр 1985 ) утверждению:

либо Г, либо К ^Г является K -раскрашиваемым для любого графа G .

Другими словами, гипотезу Хедетниеми можно рассматривать как утверждение об экспоненциальных графах: для каждого целого числа k граф K _k^Г либо является k -раскрашиваемым, либо содержит цикл (это означает, что G можно k -раскрасить). Также можно увидеть гомоморфизмы $eval : G \times K k Г \to K k$ как самые сложные примеры гипотезы Хедетниеми: если произведение G × H было контрпримером, то G × K _k^Г также будет контрпримером.

Обобщения

Обобщенная на ориентированные графы, эта гипотеза имеет простые контрпримеры, как заметили Поляк и Рёдль (1981) . Здесь хроматическое число ориентированного графа — это просто хроматическое число базового графа, но тензорное произведение имеет ровно половину количества ребер (для направленных ребер g→g' в G и h→h' в H тензор произведение G × H имеет только одно ребро, от (g,h) до (g',h') , в то время как произведение базовых неориентированных графов будет иметь ребро между (g,h') и (g',h) также). Однако слабая гипотеза Хедетниеми оказывается эквивалентной в направленных и ненаправленных настройках ( Tardif & Wehlau 2006 ).

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

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

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

Ссылки

Первоисточники

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

Опросы и вторичные источники

Имрих, Вильфрид; Клавжар, Сэнди (2000), Графики продуктов: структура и распознавание , Wiley, ISBN 0-471-37039-8 .
Калай, Гил (10 мая 2019 г.), «Сенсация в утренних новостях – Ярослав Шитов: контрпримеры к гипотезе Хедетниеми» , Комбинаторика и многое другое .
Клавжар, Санди (1996), «Раскраска графовых произведений: обзор», Discrete Mathematics , 155 (1–3): 135–145, doi : 10.1016/0012-365X(94)00377-U , MR 1401366 .
Зауэр, Н. (2001), «Гипотеза Хедетниеми: обзор», Discrete Mathematics , 229 (1–3): 261–292, doi : 10.1016/S0012-365X(00)00213-2 , MR 1815610 .
Тардиф, Клод (2008), «Гипотеза Хедетниеми, 40 лет спустя» (PDF) , Заметки по теории графов в Нью-Йорке , 54 : 46–57, MR 2445666 , заархивировано из оригинала (PDF) 12 июля 2021 г. , извлечено 23 февраля 2017 г.
Чжу, Сюдин (1998), «Обзор гипотезы Хедетниеми», тайваньский J. Math. , 2 (1): 1–24, doi : 10.11650/twjm/1500406890 , MR 1609464 .

Внешние ссылки

Прорыв в теории графов , Numberphile