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

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

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

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

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

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

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

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

Аналогично, если два графа ${\displaystyle G}$ и ${\displaystyle H}$ не раскрашиваются в два цвета, то есть не

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

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

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

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

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

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

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

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

Упомянутые выше известные случаи эквивалентны утверждениям, что графы ${\displaystyle K_{1}}$, ${\displaystyle K_{2}}$ и ${\displaystyle K_{3}}$ мультипликативны. Случай ${\displaystyle K_{4}}$ широко открыт. С другой стороны, доказательство Эль-Захара и Зауэра^[3] обобщили Хе́ггквист, Хелл, Миллер и Нойманн-Лара^[5], доказав, что все графы-циклы мультипликативны. Позднее Тардиф^[6] доказал более общий результат, что все цикловые клики ${\displaystyle K_{\tfrac {n}{k}}}$ с ${\displaystyle {\tfrac {n}{k}}<4}$ являются мультипликативными. В терминах циклового хроматического числа ${\displaystyle \chi _{c}}$ это означает, что если ${\displaystyle \chi _{c}(G\times H)<4}$, то ${\displaystyle \chi _{c}(G\times H)=\min\{\chi _{c}(G),\chi _{c}(G)\}}$.

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

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

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

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

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

Проблему нельзя обобщить на бесконечные графы — Хайнл^[8] привёл пример двух бесконечных графов, каждый из которых требует для раскраски бесконечное число красок, но их произведение можно раскрасить конечным набором цветов. Ринот^[9] доказал, что в конструктивном универсуме для любого бесконечного кардинала ${\displaystyle \kappa }$ существует пара графов с хроматическим числом, большим ${\displaystyle \kappa }$, таких, что из произведение может быть раскрашено лишь конечным числом цветов.

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

• Duffus D., Sands B., Woodrow R. E. On the chromatic number of the product of graphs // Journal of Graph Theory. — 1985. — Т. 9, вып. 4. — С. 487–495. —
  doi:10.1002/jgt.3190090409
  .
• El-Zahar M., Sauer N. The chromatic number of the product of two 4-chromatic graphs is 4 // Combinatorica. — 1985. — Т. 5, вып. 2. — С. 121–126. —
  doi:10.1007/BF02579374
  .
• Häggkvist R., Hell P., Miller D. J., Neumann-Lara V. On multiplicative graphs and the product conjecture //
  doi:10.1007/BF02122553
  .
• Hajnal A. The chromatic number of the product of two ℵ₁ chromatic graphs can be countable //
  doi:10.1007/BF02579376
  .
• Hedetniemi S. Homomorphisms of graphs and automata. — University of Michigan, 1966. — (Technical Report 03105-44-T).
• Poljak S., Rödl V. On the arc-chromatic number of a digraph //
  doi:10.1016/S0095-8956(81)80024-X
  .
• Rinot A. Hedetniemi's conjecture for uncountable graphs. — 2013. — Bibcode: 2013arXiv1307.6841R. — arXiv:1307.6841.
• Sabidussi G. Graphs with given group and given graph-theoretical properties //
  doi:10.4153/CJM-1957-060-7
  .
• Tardif C. Multiplicative graphs and semi-lattice endomorphisms in the category of graphs //
  doi:10.1016/j.jctb.2005.06.002
  .
• Tardif C., Wehlau D. Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function //
  doi:10.1002/jgt.20117
  .
• Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
• Sandi Klavžar. Coloring graph products: a survey //
  doi:10.1016/0012-365X(94)00377-U
  .
• Sauer N. Hedetniemi's conjecture: a survey //
  doi:10.1016/S0012-365X(00)00213-2
  .
• Claude Tardif. Hedetniemi's conjecture, 40 years later // Graph Theory Notes of New York. — 2008. — Т. 54. — С. 46—57.
• Xuding Zhu. A survey on Hedetniemi's conjecture // Taiwanese J. Math.. — 1998. — Т. 2, вып. 1. — С. 1–24.

• A Breakthrough in Graph Theory - Numberphile на YouTube

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (8 февраля 2019) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (8 февраля 2019) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.