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

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

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

где  — хроматическое число неориентированного конечного графа .

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

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

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

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

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

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

Следующий случай доказали много позже формулировки гипотезы Эль-Захар и Зауэр[3] — если произведение можно раскрасить в 3 цвета, то один из графов или должен также позволять раскраску в 3 цвета. В частности, гипотеза верна, когда или позволяет раскраску в 4 цвета (поскольку тогда неравенство может быть строгим, только когда позволяет раскраску в 3 цвета). В остальных случаях оба графа в тензорном произведении должны иметь по меньшей мере 5-цветную раскраску и дальнейший прогресс есть только в очень ограниченных ситуациях.

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

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

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

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

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

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

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

Упомянутые выше известные случаи эквивалентны утверждениям, что графы , и мультипликативны. Случай широко открыт. С другой стороны, доказательство Эль-Захара и Зауэра[3] обобщили Хе́ггквист, Хелл, Миллер и Нойманн-Лара[5], доказав, что все графы-циклы мультипликативны. Позднее Тардиф[6] доказал более общий результат, что все цикловые клики с являются мультипликативными. В терминах циклового хроматического числа это означает, что если , то .

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

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

Поскольку тензорное произведение графов является категорийно-теоретическим произведением в категории графов (с графами как объекты и гомоморфизмами в качестве стрелок), гипотезу можно переформулировать в терминах следующего построения на графах и . Экспоненциальный граф  — это граф со всеми функциями в качестве вершин (не только гомоморфизмы) и две функции и смежны, если вершина смежна вершине в для всех смежных вершин графа . В частности, имеется петля у функции (она смежна себе самой) тогда и только тогда, когда имеется гомоморфизм из в . Рассматривая под другим углом, можно сказать, что между и имеется ребро, когда две функции определяют гомоморфизм из (Двойное покрытие двудольным графом графа ) в .

Экспоненциальный граф является экспоненциалом в категории графов. Это означает, что гомоморфизмы из в граф соответствуют гомоморфизмам из в . Более того, имеется гомоморфизм , задаваемый выражением . Эти свойства позволяют заключить, что мультипликативность графа эквивалентна утверждению[3]: для любых графов и либо , либо является -раскрашиваемым.

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

Обобщения

Обобщение на ориентированные графы имеет простой контрпример, как показали Поляк и Рёдль[4]. Хроматическое число ориентированного графа является просто хроматическим числом соответствующего неориентированного графа, но тензорное произведение имеет в точности половину числа рёбер (для дуг в и в тензорное произведение имеет только одно ребро из в , в то время как произведение неориентированных графов имеет также ребро между и ). Однако оказывается, что слабая гипотеза Хедетниеми эквивалентна для неориентированных и ориентированных графов[7].

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

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

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

Примечания

  1. Владимир Потапов. В поисках хроматического числа. N+1 (30 мая 2019). Дата обращения: 30 мая 2019.
  2. Yaroslav Shitov. Counterexamples to Hedetniemi's conjecture (англ.) // Annals of Mathematics. — 2019. — September (vol. 190, iss. 2). — P. 663-667. doi:10.4007/annals.2019.190.2.6. arXiv:1905.02167.
  3. El-Zahar, Sauer, 1985.
  4. Poljak, Rödl, 1981.
  5. Häggkvist, Hell, Miller, Neumann-Lara, 1988.
  6. Tardif, 2005.
  7. Tardif, Wehlau, 2006.
  8. Hajnal, 1985.
  9. Rinot, 2013.
  10. Sabidussi, 1957.
  11. Duffus, Sands, Woodrow, 1985.

Литература

Основные источники
  • 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 ℵ1 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. — . 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.
Обзоры и другие источники
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.