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

Пример, для которого выполняется гипотеза Хедетниеми — тензорное произведение $C_5$ и $C_3$ (слева) даёт граф, который содержит цикл длиной 15 (справа), так что получающийся граф требует для раскраски 3 цвета.

Гипотеза Хедетниеми — математическая гипотеза, в общем случае опровергнутая, предположение о связи между раскраской графов и тензорным произведением графов:

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

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

Сформулирована Стефеном Хедетниеми в 1966 году.

В 2019 году российский математик Ярослав Шитов опровергнул гипотезу, предложив контрпример к ней.

Неравенство $\chi (G\times H)⩽\min \{\chi (G),\chi (H)\}$ подтвердить просто — если граф $G$ раскрашен в $k$ цветов, $G\times H$ можно раскрасить в $k$ цветов путём использования той же раскраски для каждой копии $G$ в произведении, из симметричного рассуждения следует ограничение по $H$. Таким образом, гипотеза Хедетниеми утверждает, что тензорные произведения не могут быть раскрашены с неожиданно малым числом цветов.

Частные случаи, в которых гипотеза верна

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

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

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

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

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

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

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

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

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

Гипотеза изучается в более общем контексте гомоморфизмов графов, особенно ввиду её связи с категорией графов (с графами как объекты и гомоморфизмами в качестве стрелок). Для любого фиксированного графа $K$ рассматриваются графы $G$, которые допускают гомоморфизм в $K$, что записывается как $G\to K$. Такие графы называются также $K$-раскрашиваемыми. Это обобщает обычное понятие раскраски графов, поскольку из определения следует, что $k$-раскраска является тем же самым, что и $K_k$-раскраска (гомоморфизм в полный граф с $k$ вершинами).

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

Упомянутые выше известные случаи эквивалентны утверждениям, что графы $K_1$, $K_2$ и $K_3$ мультипликативны. Случай $K_4$ широко открыт. С другой стороны, доказательство Эль-Захара и ЗауэраШаблон:Sfn обобщили Хе́ггквист, Хелл, Миллер и Нойманн-ЛараШаблон:Sfn, доказав, что все графы-циклы мультипликативны. Позднее ТардифШаблон:Sfn доказал более общий результат, что все цикловые клики $K_{\frac{n}{k}}$ с $\frac{n}{k}<4$ являются мультипликативными. В терминах циклового хроматического числа ${\chi }_c$ это означает, что если ${\chi }_c(G\times H)<4$, то ${\chi }_c(G\times H)=\min \{{\chi }_c(G),{\chi }_c(G)\}$.

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

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

Поскольку тензорное произведение графов является категорийно-теоретическим произведением в категории графов (с графами как объекты и гомоморфизмами в качестве стрелок), гипотезу можно переформулировать в терминах следующего построения на графах $K$ и $G$. Экспоненциальный граф $K^G$ — это граф со всеми функциями $V(G)\to V(K)$ в качестве вершин (не только гомоморфизмы) и две функции $f$ и $g$ смежны, если вершина $f(v)$ смежна вершине $g(v^{\prime })$ в $K$ для всех смежных вершин $v,v^{\prime }$ графа $G$. В частности, имеется петля у функции $f$ (она смежна себе самой) тогда и только тогда, когда имеется гомоморфизм из $G$ в $K$. Рассматривая под другим углом, можно сказать, что между $f$ и $g$ имеется ребро, когда две функции определяют гомоморфизм из $G\times K_2$ (Двойное покрытие двудольным графом графа $G$) в $K$.

Экспоненциальный граф является экспоненциалом в категории графов. Это означает, что гомоморфизмы из $G\times H$ в граф $K$ соответствуют гомоморфизмам из $H$ в $K^G$. Более того, имеется гомоморфизм $\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}:G\times K^G\to K$, задаваемый выражением $\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}(v,f)=f(v)$. Эти свойства позволяют заключить, что мультипликативность графа $K$ эквивалентна утверждениюШаблон:Sfn: для любых графов $G$ и $K$ либо $G$, либо $K^G$ является $K$-раскрашиваемым.

Другими словами, гипотезу Хедетниеми можно рассматривать как утверждение об экспоненциальных графах — для любого целого $k$ граф $K_k^G$ либо $k$-раскрашиваем, либо содержит петлю (это означает, что $G$ является $k$-раскрашиваемым). Можно также видеть гомоморфизмы $\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}:G\times K_k^G\to K_k$ как самые трудные случаи гипотезы Хедетниеми — если произведение $G\times H$ было бы контрпримером, то и $G\times K_k^G$ было бы контрпримером.

Обобщения

Обобщение на ориентированные графы имеет простой контрпример, как показали Поляк и РёдльШаблон:Sfn. Хроматическое число ориентированного графа является просто хроматическим числом соответствующего неориентированного графа, но тензорное произведение имеет в точности половину числа рёбер (для дуг $g\to g^{\prime }$ в $G$ и $h\to h^{\prime }$ в $H$ тензорное произведение $G\times H$ имеет только одно ребро из $(g,h)$ в $(g^{\prime },h^{\prime })$, в то время как произведение неориентированных графов имеет также ребро между $(g,h^{\prime })$ и $(g^{\prime },h)$). Однако оказывается, что слабая гипотеза Хедетниеми эквивалентна для неориентированных и ориентированных графовШаблон:Sfn.

Проблему нельзя обобщить на бесконечные графы — ХайнлШаблон:Sfn привёл пример двух бесконечных графов, каждый из которых требует для раскраски бесконечное число красок, но их произведение можно раскрасить конечным набором цветов. РинотШаблон:Sfn доказал, что в конструктивном универсуме для любого бесконечного кардинала $\kappa$ существует пара графов с хроматическим числом, большим $\kappa$, таких, что из произведение может быть раскрашено лишь конечным числом цветов.

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

Похожее равенство для прямого произведения графов доказал СабидуссиШаблон:Sfn и оно было переоткрыто после этого несколько раз. Точная формула известна для лексикографического произведения графов. Дуффус, Сэндс и ВудроуШаблон:Sfn предложили две более строгие гипотезы с единственностью раскраски.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:YouTube