WikiSort.ru - Не сортированное

Нерешённые проблемы математики: Может ли хроматическое число тензорного произведения двух графов быть меньше, чем хроматическое число обоих множителей?

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

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

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

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

Неравенство ${\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}$ не раскрашиваются в 2 два цвета, то есть не двудольный, тогда оба содержат цикл нечётной длины. Поскольку произведение двух нечётных циклов содержит нечётный цикл, произведение ${\displaystyle G\times H}$ также не может быть раскрашено в 2 цвета. Другими словами, если ${\displaystyle G\times H}$ можно раскрасить в 2 цвета, то по меньшей мере один из графов ${\displaystyle G}$ или ${\displaystyle H}$ должен позволять раскраску в 2 цвета.

Следующий случай доказали много позже формулировки гипотезы Эль-Захар и Зауэр^[1] — если произведение ${\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)}$ не ограничена. Другими словами, если тензорное произведение двух графов можно раскрасить в несколько цветов, из этого должно следовать ограничение на хроматическое число одного из множителей.

Главный результат Поляка и Рёдля^[2], независимо улучшенный Поляком, Шмерлем и Зу, утверждает, что если функция ${\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}}$ широко открыт. С другой стороны, доказательство Эль-Захара и Зауэра^[1] обобщили Хе́ггквист, Хелл, Миллер и Нойманн-Лара^[3], доказав, что все графы-циклы мультипликативны. Позднее Тардиф^[4] доказал более общий результат, что все цикловые клики ${\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}$ эквивалентна утверждению^[1]: для любых графов ${\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}}$ было бы контрпримером.

Обобщения

Обобщение на ориентированные графы имеет простой контрпример, как показали Поляк и Рёдль^[2]. Хроматическое число ориентированного графа является просто хроматическим числом соответствующего неориентированного графа, но тензорное произведение имеет в точности половину числа рёбер (для дуг ${\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)}$ ). Однако оказывается, что слабая гипотеза Хедетниеми эквивалентна для неориентированных и ориентированных графов^[5].

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

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

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

Примечания

Литература

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

• 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 // Combinatorica. — 1988. — Т. 8, вып. 1. — С. 63–74. — DOI:10.1007/BF02122553.
• Hajnal A. The chromatic number of the product of two ℵ₁ chromatic graphs can be countable // Combinatorica. — 1985. — Т. 5, вып. 2. — С. 137–140. — 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 // Journal of Combinatorial Theory, Series B. — 1981. — Т. 31, № 2. — С. 190—198. — 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 // Canadian Journal of Mathematics. — 1957. — Т. 9. — С. 515–525. — DOI:10.4153/CJM-1957-060-7.
• Tardif C. Multiplicative graphs and semi-lattice endomorphisms in the category of graphs // Journal of Combinatorial Theory, Series B. — 2005. — Т. 95, № 2. — С. 338—345. — 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 // Journal of Graph Theory. — 2006. — Т. 51, № 1. — С. 33—36. — 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 // Discrete Mathematics. — 1996. — Т. 155, вып. 1–3. — С. 135–145. — DOI:10.1016/0012-365X(94)00377-U.
• Sauer N. Hedetniemi's conjecture: a survey // Discrete Mathematics. — 2001. — Т. 229, вып. 1–3. — С. 261–292. — 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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.