Российский математик Ярослав Шитов опроверг гипотезу Стефана Хидетниеми о хроматическом числе тензорного произведения графов

Несколько дней назад сообщество математиков — специалистов в теории графов было взволновано сообщением о том, что выдвинутая Стефеном Хидетниеми (Stephen T. Hedetniemi) в 1966 году гипотеза оказалась неверной. Оказывается, хроматическое число тензорного произведения двух графов может быть меньше минимума хроматических чисел сомножителей, а не всегда равно этому минимуму, как когда-то предположил Хидетниеми. Как построить контрпример к этой гипотезе, придумал молодой московский математик Ярослав Шитов. Подробнее об этом по просьбе N+1 рассказал математик Владимир Потапов.

Хроматическое число графов

Расскажем подробнее о том, что такое хроматическое число графа, тензорное произведение графов и почему более 50 лет эта гипотеза казалась верной большинству специалистов.

Начнем с того, что графом в математике называется набор точек (вершин графа), соединенных отрезками (ребрами графа). Раскраска вершин графа в разные цвета называется правильной, если вершины, соединенные ребром (смежные вершины), раскрашены в разные цвета.

Граф Петерсена

Хроматическим числом графа называется минимальное число цветов, которыми можно правильно раскрасить вершины графа. Нетрудно видеть, что изображенный выше граф Петерсена нельзя правильно раскрасить в два цвета, поскольку в нем есть циклы нечетной длины. Следовательно, его хроматическое число равно $3$ .

Задача нахождения хроматического числа графа стала популярной благодаря широко известному вопросу: «Можно ли вершины плоского (то есть размещенного на плоскости без пересечений ребер) графа правильно раскрасить в 4 цвета?»

Гипотеза «четырех красок», которая состоит в положительном ответе на этот вопрос, возникла еще в XIX веке и была доказана Кеннетом Аппелем и Вольфгангом Хакеном только в 1977 году. Причем в доказательстве авторам пришлось прибегнуть к компьютеру, чтобы правильно раскрасить сотни графов, раскраска которых уже не сводилась к раскраске более простых графов. Кстати, граф Петерсена плоским не является и может быть нарисован на плоскости только с пересечениями ребер.

Может показаться, что игры в раскрашивание графов не могут иметь никакого полезного применения. Даже практический вопрос: сколько необходимо цветов, чтобы любые соседние страны на карте были разного цвета? — из которого возникла гипотеза о «четырех красках», кажется скорее праздным, чем полезным. Однако по мере роста сложности инфраструктуры и оборудования оказалось, что имеется множество вполне серьезных задач, которые сводятся к нахождению хроматического числа графа.

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

Если же рассмотреть социальную сеть Facebook как граф с вершинами — пользователями, каждая из которых смежна с «друзьями», то становится ясно, что изучение различных характеристик графов важно для понимания закономерностей распространения информации (новостей, моды, инноваций) в современном мире.

Произведения графов

Прежде чем перейти к обсуждению гипотезы Хидетниеми, поговорим о понятии декартова произведения графов. Пусть имеются два графа $G$ и $H$ с множествами вершин $\{u_1,\dots,u_n\}$ и $\{v_1,\dots,v_m\}$ соответственно. Тогда их декартовым произведением называется граф, вершины которого являются всевозможными парами $(u_i,v_k)$ . Причем вершины $(g,h)$ и $(b,d)$ соединены ребром, только если $g=b$ и вершина $h$ смежна с вершиной $d$ в графе $H$ или, наоборот, $h=d$ и вершина $g$ смежна с вершиной $b$ в графе $G$ .

Декартово произведение графов

Легко понять, что хроматическое число декартова произведения графов не меньше, чем хроматическое число любого из сомножителей. Если мы зафиксируем любую вершину $h$ графа $H$ и рассмотрим в декартовом произведении вершины вида $(u,h)$ , а также ребра между ними, то получится такой же подграф, как граф $G$ . Значит, для правильной раскраски этого подграфа нужно столько же цветов, сколько для правильной раскраски графа $G$ , а для правильной раскраски всего декартова произведения цветов нужно точно не меньше. То же самое можно сказать и про граф $H$ .

Более 50 лет назад математик Герт Сабидусси доказал, что хроматическое число декартова произведения графов равно максимуму хроматических чисел сомножителей.

Теперь перейдем к тензорному произведению графов, о котором говорится в гипотезе Хидетниеми. Тензорным произведением графов $G$ и $H$ называется граф с теми же вершинами, что и у декартова произведения графов $G$ и $H$ , которые, однако, по-другому соединены ребрами. А именно, вершины $(g,h)$ и $(b,d)$ в тензорном произведении соединены ребром, только если вершина $g$ смежна с вершиной $b$ в графе $G$ и вершина $h$ смежна с вершиной $d$ в графе $H$ .

Тензорное произведение графов

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

Действительно, если покрасить каждую вершину $(u,v)$ тензорного произведения в тот цвет, в который была покрашена вершина $u$ графа $G$ , то любая смежная с ней вершина $(g,h)$ окажется покрашена в другой цвет, поскольку вершины $u$ и $g$ были смежны в графе $G$ и его раскраска была правильной. Значит, цвета вершин $(u,v)$ и $(g,h)$ , так же как вершин $u$ и $g$ , различны. Поэтому хроматическое число тензорного произведения не превосходит минимума хроматических чисел сомножителей.

Правильная раскраска тензорного произведения графов

Сильным произведением двух графов $G_1$ и $G_2$ называется граф с тем же множеством вершин, как у декартова и тензорного произведения этих графов. Ребрами сильного произведения графов являются одновременно ребра декартова и тензорного произведений.

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

Естественно предположить, что хроматическое число тензорного произведения будет в точности равно минимуму хроматических чисел сомножителей. Ведь каждая вершина тензорного произведения графов имеет гораздо больше соседей, чем было у вершин исходных графов! Тем более что в похожем случае декартова произведения имеется равенство.

Это естественное предположение и сделал Хидетниеми. И оно подтверждалось практически для различных частных случаев, Например, граф на иллюстрации выше имеет циклы нечетной длины, а значит, его хроматическое число не меньше трех. И даже теоретически для некоторых классов графов было доказано, что гипотеза Хидетниеми верна, например для тензорного произведения любых двух графов с хроматическими числами не более $4$ .

Круг графов, для которых удалось проверить правильность гипотезы Хидетниеми постепенно расширялся и казалось, что вот-вот гипотеза будет доказана полностью.

Однако Ярославу Шитову неожиданно удалось доказать обратное. Причем не посредством построенного с помощью компьютера контрпримера, а полностью теоретически.

Для того чтобы кратко описать его доказательство, нам понадобится несколько определений. Во-первых, для произвольного графа $H$ определим экспоненциальный граф $E_s(H)$ . Вершинами графа $E_s(H)$ будут функции, действующие из множества вершин графа $H$ в множество чисел $\{1,\dots, s\}$ . Две функции $f$ и $g$ будем считать смежными, если они принимают различные значения на любых вершинах, смежных в графе $H$ .

Нетрудно убедиться, что тензорное произведение графов $H$ и $E_s(H)$ можно правильно раскрасить в $s$ цветов, независимо от хроматического числа графа $H$ . Определим раскраску вершины $(u,f)$ тензорного произведения равной $f(u)$ . Рассмотрим пару вершин $(u,f)$ и $(v,g)$ смежных в тензорном произведении графов. Тогда вершины $u$ и $v$ смежны в $H$ , а вершины $f$ и $g$ смежны в $E_s(H)$ . Значит, по определению экспоненциального графа числа $f(u)$ и $g(v)$ не совпадают, то есть так определенная раскраска тензорного произведения в $s$ цветов является правильной.

Теперь нужно найти подходящий граф $H$ , чтобы хроматические числа графа $H$ и его экспоненциального графа $E_s(H)$ были строго больше $s$ .

Классическая теорема Пала Эрдеша утверждает, что найдутся графы со сколь угодно большим хроматическим числом и сколь угодно большим обхватом (минимальным циклом).

Рассмотрим граф $G$ с обхватом $10$ и хроматическим числом $5$ . Полным графом $K_q$ , или $q$ -кликой, называется граф на $q$ вершинах, все вершины которого попарно соединены ребрами.

Определим граф $H$ как сильное произведение графов $G$ и $K_q$ . Граф $H$ получается подстановкой $q$ -клик во все вершины графа $G$ , причем все вершины смежных $q$ -клик попарно соединены ребрами. Отсюда нетрудно доказать, что хроматическое число сильного произведения графа $G$ на $q$ -клику будет иметь хроматическое число не меньше чем $5q$ .

Ярославу Шитову удалось доказать, что для достаточно больших $q$ и $s > 4{,}1q$ экспоненциальный граф $E_s(H)$ имеет хроматическое число строго большее, чем $s$ . Теперь достаточно выбрать такое $s$ , что $5q > s > 4{,}1q$ и мы получаем, что оба сомножителя $H$ и $E_s(H)$ в тензорном произведении имеют хроматические числа больше, чем $s$ , а их тензорное произведение имеет хроматическое число равное $s$ , как было доказано выше. Таким образом, гипотеза Хидетниеми опровергнута.

Слово автору опровержения

Я не уверен, что у специалистов было единое мнение о том, верна ли гипотеза Хидетниеми: некоторые исследователи считали ее верной, но были и те, кто считал иначе. В пользу истинности гипотезы говорили случаи графов с хроматическим числом не больше четырех (подробнее); графов с большими кликами (подробнее здесь, здесь и здесь), графов и гиперграфов Кнезера (подробнее), а также аналог гипотезы Хидетниеми для дробных раскрасок. Тем не менее, аналогичное утверждение оказывается неверным для бесконечных графов: контрпример был найден еще в 1985 году.

Как и многие математические задачи и результаты, гипотеза Хидетниеми появилась и активно изучалась, как мне кажется, из чистого любопытства. Говорить о том, что из нее следовали какие-то важные выводы за пределами «чистой математики», которые теперь придется пересматривать, я бы не стал.

На языке гомоморфизмов гипотеза Хидетниеми звучит так: все полные графы являются мультипликативными (граф $K$ называется мультипликативным, если существование гомоморфизма из тензорного произведения графов $G$ и $H$ в граф $K$ влечет наличие гомоморфизма из $G$ в $K$ или гомоморфизма из $H$ в $K$ ). Понятие мультипликативности активно обсуждается и для других графов, но ситуация с достаточно большими кликами стала ясна лишь теперь. Были еще и топологические следствия из гипотезы Хидетниеми, но, так как гипотеза не подтвердилась, они остаются открытыми проблемами.

(Ярослав Шитов для N+1)

Владимир Потапов
N+1

Комментарии: 0

Похожее

О шарнирных механизмах, раскрашенных графах и вывернутых наизнанку многогранниках

Гаянэ Панина

Вот три тесно связанные между собой задачи, которые мы будем обсуждать: Как распрямить плотницкую линейку? Можно ли нарисовать на сфере правильно раскрашенный граф? Верна ли старая гипотеза А. Д. Александрова о характеризации сферы? Попутно будет сформулировано много задач разного уровня сложности (именно исследовательских задач, а не упражнений!). Часть из них — для умеющих и любящих программировать. В курсе будет много картинок.
Теория графов

Андрей Райгородский

Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям человеческого мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В этом курсе будут обсуждены классические задачи и некоторые недавние результаты и тенденции, например, экстремальная теория графов.
Как посчитать детские рисунки?

Георгий Шабат

Детские рисунки (dessins d'enfants) – термин, введённый Александром Гротендиком в 70-е годы прошлого века. С «детской» точки зрения этот термин означает граф, вложенный в поверхность; с взрослой – это объект, в котором закодированы различные структуры, относящиеся к далёким друг от друга областям математики. Под подсчётом детских рисунков понимается подсчёт количества детских рисунков ограниченной сложности, которая будет определена. В последние годы были получены замечательные результаты о количествах детских рисунков. Элементарная часть этих результатов будет изложена в курсе.
Целые точки в выпуклых многогранниках

Гаянэ Панина

Курс представляет собой букет из трёх очень старых и трёх очень новых идей. Основной объект — число целых (т.е. с целыми координатами) точек в многограннике. Зачем нужны целые точки? Несколько примеров: многогранник Ньютона, Теорема Бриона — для начала без доказательства, просто в качестве фокуса, а также подсчёт целых метрических ленточных графов. Число целых точек в выпуклом многограннике ведёт себя как полином. Согласно конструкции, в полином, вычисляющий число целых точек, имеет смысл подставлять лишь положительные числа. Чтобы придать смысл отрицательной подстановке, нужны виртуальные многогранники. Двойственность Эрхарта и её естественное обобщение. Секрет фокуса Бриона.
Графы и квантовая механика: симплектические идеи

Сергей Новиков

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

Александр Буфетов, Александр Комлов

Рассмотрим конечный связный граф. Сколько в нем остовных деревьев — деревьев, содержащих все вершины графа? А какая их доля содержит данный набор ребер? Цель нашего курса — дать элементарное введение в теорию детерминантных процессов. Мы планируем обсудить недавние достижения и сформулировать нерешенные проблемы. Программа занятий: детерминанты и пфаффианы; остовные деревья; случайные матрицы; мультипликативные функционалы.
Джун Ху — математический гений, который поздно созрел, но всех одолел

Теплым весенним утром Джун Ху шел в зал Макдоннелла Пристонского университета, где его ждали студенты. Однако он не был уверен, что идет в нужном направлении. Ху работает в элитарном Институте перспективных исследований, который располагается неподалеку от студгородка Принстона. Будучи сотрудником института, Ху не обязан преподавать. Тем не менее, он вызвался прочитать студентам продвинутый курс по коммутативной алгебре.
Головоломка середины XIX века помогла сформировать новое направление математики

В 1850 году преподобный Томас Киркман, британский математик и настоятель прихода в Ланкашире, сформулировал невинно выглядящую головоломку в развлекательном журнале для любителей математики. Задачка выглядит простой, но если попробовать её решить, то сразу понимаешь, что это не так. В силу своей ложной простоты задача быстро стала знаменитой. Свои решения присылали любители математики, а учёные публиковали научные статьи с попыткой сформулировать общее решение для проблемы. В результате, эта головоломка помогла сформировать новое направление математики.
Окраска глазчатых ящериц порождается клеточным автоматом

Татьяна Романовская

Окраска многих животных устроена причудливо и замысловато. На клеточном уровне ее возникновение описывается реакционно-диффузными моделями при помощи систем дифференциальных уравнений. В недавней работе группа ученых из Швейцарии детально изучила механизм формирования окраски глазчатых ящериц Timon lepidus. Оказалось, что это происходит по правилам, характерным для дискретного клеточного автомата, где в роли ячеек автомата выступают отдельные чешуйки кожи ящериц. Математическое моделирование позволило понять, что реакционно-диффузная система может порождать клеточный автомат благодаря особым условиям — в данном случае это подходящие размеры чешуек и толщина кожи ящериц внутри и на границе чешуек.
Как обнаружить фальшивую монету

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

Далее >>>

∀ x, y, z

Российский математик Ярослав Шитов опроверг гипотезу Стефана Хидетниеми о хроматическом числе тензорного произведения графов

Теги

Похожее