[Перевод] Российский математик опроверг 53-летнюю гипотезу о раскраске сетей
Всего три страницы потребовалось российскому математику, чтобы описать способ раскраски сетей определённого типа, превзошедший ожидания экспертов
В опубликованной в онлайне работе опровергается гипотеза 53-летней давности, касающаяся наилучшего способа назначения цветов узлам сети. В работе всего на трёх страничках показано существование способов раскраски определённых цветов, превзошедших все ожидания экспертов.
Задачи по раскраске сетей [см. хроматическое число / прим. перев.], вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет. Задача состоит в том, чтобы понять, как раскрашивать узлы некоей сети (или графа, как зовут их математики) так, чтобы у любых двух связанных узлов были разные цвета. В зависимости от контекста, эта раскраска может предоставить эффективный способ рассадки гостей на свадьбе, расстановке производственных задач по свободным временным промежуткам, или даже решения судоку.
Задачи по раскраске графов часто легко сформулировать, однако невероятно трудно решить. Даже на поиски ответа на вопрос, с которого началась вся эта область исследований — достаточно ли четырёх цветов для раскраски любой карты? — ушло более ста лет (если вам интересно, то ответ — да).
Задача, рассматривавшаяся в новой работе, до сей поры не считалась исключением. Её не могли решить более 50 лет, и она касается тензорных произведений — графов, составленных из особой комбинации двух разных графов (назовём их G и H). Тензорное произведение графов G и H — это новый, более крупный граф, каждая вершина которого обозначает пару вершин оригинальных графов — одну от G и одну от H — при этом две вершины тензорного произведения соединены, если соединены как соответствующие им вершины в G, так и соответствующие им вершины в H.
Предположим, вы — преподаватель музыки, и вам нужно найти хорошие дуэтные пары для концерта пятого курса. Вы можете составить граф, вершинами которого будут студенты, а связи между парами будут обозначать наличие хороших отношений между ними. Затем вы можете составить второй граф, в котором каждый узел будет обозначать различные музыкальные инструменты, а связь между ними — наличие у вас нотных листов для дуэта двух этих инструментов. В тензорном произведении двух этих графов будет по одной вершине для каждого возможного объединения студента и инструмента (допустим, Алиса и тромбон), а две вершины будут связаны, если два студента хорошо работают вместе, и при этом два инструмента совместимы.
В 1966 году Стивен Хедетниеми, сегодня работающий профессором в Университете Клемсона в Южной Каролине, в своей докторской диссертации выдвинул предположение, что минимальное количество цветов, необходимое для раскраски тензорного произведения, равняется наименьшему из двух количеств цветов, необходимых для раскраски любого из двух составляющих его графов. «Это одна из основных гипотез в теории графов, — сказал Гил Калай из Еврейского университета в Иерусалиме. — Её пыталось обдумывать много людей».
За прошедшие десятилетия математики собрали гору свидетельств, некоторые из которых говорили об истинности гипотезы, а некоторые — о её ложности. У разных математиков были разные предположения по поводу того, какой из вариантов в итоге победит. Но все соглашались, что, по крайней мере, это сложная задача.
«Лично я считал, что эта гипотеза верна, поскольку огромное количество умных людей изучали её, и должны были бы придумать контрпример», если бы такой существовал, сказал Энтони Бонато из Университета Райерсона в Торонто.
И вот российский математик Ярослав Николаевич Шитов придумал простой способ создания контрпримеров, тензорных произведений, которым требуется меньше цветов, чем любому из двух составляющих их графов. Доказательство вышло «элементарным, но гениальным», сказал Павол Хелл из университета Саймона Фрейзера в Бёрнаби (Канада).
Тензорные графы тесно связаны с вопросами об отображениях разных графов друг на друга, и в этой области математики гипотеза Хедетниеми была, вероятно, крупнейшей из открытых проблем, сказал Хелл. «Это важнейший прорыв».
Цветастые сборища
Чтобы представить, какую информацию можно извлечь из раскрашивания тензорного графа, представьте, что вы собираетесь каждые выходные приглашать своих друзей в своё загородное поместье. И, как хорошему хозяину, вам хочется собрать людей, которые будут получать удовольствие от компании друг друга.
Вы знаете, что некоторые из ваших друзей смогут быстро подружиться на почве работы, а другие — нет. Также вы знаете, что у ваших друзей есть хобби — ещё один способ, через который гости смогут найти общие интересы. Вы размышляете, что преподаватель танцев, играющий на скрипке, может хорошо провести время, беседуя с инструктором по йоге, играющим в теннис, или обсуждая музыку с фермером, добывающим кленовый сироп, и играющим на пианино, но при этом, вероятно, ему не о чем будет говорить с политологом, коллекционирующим марки. Вы хотите, чтобы на любых выходных каждая пара гостей смогла найти некие общие интересы, будь то работа или хобби, и вам интересно, сколько сборищ нужно устроить, чтобы перебрать всех гостей из списка.
Ярослав Шитов обнаружил контрпример гипотезе Хедетниеми 53-летней давности из области теории графов
Взаимоотношения различных видов работы вы могли бы представить в виде графа, узлами которого будут работы, а рёбрами будут соединяться две любых работы, между которыми, скорее всего, нельзя будет найти общих тем для разговора (такой подход может показаться вывернутым наизнанку, однако в контексте раскраски графов такое соединение вершин имеет смысл, поскольку мы будем использовать цвета для разделения этих проблемных пар). Также вы могли бы сделать граф, вершинами которого служат разные хобби, и соединить между собой все несовместимые.
У тензорного произведения двух этих графов будут узлы для каждой пары работа-хобби, а две вершины будут объединяться, если как обе работы, так и оба хобби несовместимы — это как раз та ситуация, которой вы хотите избежать на выходных. Если вы сможете раскрасить вершины тензорного произведения так, чтобы у соединённых рёбрами вершин были разные цвета, это даст вам способ формирования списков гостей на разные выходные: вы можете пригласить людей, соответствующих зелёным вершинам, в «зелёные» выходные, красным вершинам — в «красные», и так далее, и быть уверенным в том, что несовместимые гости окажутся в списках на разных выходных. Количество использованных вами цветов сообщит вам, сколько выходных нужно будет занять в календаре.
Из этого примера следует, что любая допустимая раскраска графа работ переносится и на тензорное произведение — вы можете просто раскрасить каждую комбинацию работа-хобби тем же цветом, что вы использовали и для работы. Такая раскраска приведёт к тому, что на сборищах каждая пара гостей будет совместима исключительно по профессиональным интересам, вне зависимости от их хобби.
И наоборот, любая допустимая раскраска графа хобби переносится и на тензорное произведение. Хедетниеми предположил, что наилучшим способом раскрасить тензорный граф будет минимальная по количеству цветов раскраска одного из изначальных графов.
На первый взгляд, гипотеза Хедетниеми кажется маловероятной. Ведь если вы основываете тензорную раскраску на раскраске рабочего графа, вы игнорируете всё, что вы знаете о совместимых хобби ваших друзей, и потенциально разделяете гостей, которые бы поладили друг с другом. Если же вы скомбинируете всю информацию о работах и хобби, возможно, вам удастся использовать меньше цветов и насладиться заслуженными выходными без гостей.
И всё же в течение более чем 50 лет математики не могли найти ни одного тензорного произведения, для раскраски которого требовалось бы меньше цветов, чем для любого из составляющих его графов. Они смогли доказать, что гипотеза верна, если для раскраски одного из двух графов требовалось не более четырёх цветов. Она также верна в более общем случае «дробных» раскрасок, когда каждой вершине можно назначать комбинацию из цветов — например, 2/3 жёлтого и ⅓ зелёного. (В терминах выходных сборищ это может соответствовать ситуации, когда в вашем списке друзей есть три журналиста, один из которых играет в теннис, и вы пригласили двух из них на «жёлтые» выходные, а третьего — на «зелёные»).
Эти открытия подсказывали, что гипотеза может быть истинной, однако другие говорили о противоположном. К примеру, математики показали, что гипотеза Хедетниеми разваливается для графов, которым требуется бесконечное количество цветов для раскраски, или для направленных графов, у рёбер которых есть предпочтительные направления. Но, несмотря на то, что математики доказали гипотезу Хедетниеми для каких-то случаев, и опровергли для других, они не смогли решить вопрос в той области, которую изначально рассматривал сам Хедетниеми: конечные ненаправленные графы с целочисленной раскраской.
«Все в целом считали её верной, однако доказать или опровергнуть это было сложно», — сказал Нога Элон из Принстонского университета.
Раскрашивая страницы
Шитов разбил все эти неопределённости при помощи чёткой и простой демонстрации ложности гипотезы Хедетниеми. В работе, основное доказательство которой умещается на одной странице, под завязку забитой математикой, он показывает, как создать особый тип тензорного произведения, для раскраски которого требуется меньше цветов, чем для любого из его составляющих.
Шитов начинает работу с наблюдения за тем, что произойдёт, если скомбинировать граф G с одним из его экспоненциальных графов, и получить их тензорное произведение. У экспоненциального графа имеется по одному узлу для каждой из возможных раскрасок G неким фиксированным количеством цветов (разрешаются все возможные раскраски, не только те, у которых соединённые вершины имеют разные цвета). Если у графа G, допустим, 7 вершин, а в нашей палитре 5 цветов, тогда у экспоненциального графа будет 57 вершин — поэтому он и называется экспоненциальным.
Гипотеза Стивена Хедетниеми о минимальном количестве цветов для раскраски тензорного произведения графов оставалась неподтверждённой более 50 лет
Если вернуться к варианту раскраски, в котором связанные вершины должны быть разных цветов, то у нас не будет гарантии, что пяти цветов нашей палитры будет достаточно для раскраски графа G, и точно так же их может не хватить для раскраски экспоненциального графа с 57 вершин. Однако математикам давно известно, что существует один граф, для раскраски которого достаточно пяти цветов: это тензорное произведение, состоящее из G и его экспоненциального графа.
На самом деле, у всех экспоненциальных графов есть это свойство: тензорное произведение, комбинирующее экспоненциальный граф с графом, на основе которого он был создан, можно раскрасить ровно таким же количеством цветов, как и оригинальный граф. Шитов опроверг гипотезу Хедетниеми, показав, как можно создать такой граф G, что для раскраски как его, так и его экспоненциального графа требуется больше цветов.
Хедетниеми заявил, что «совершенно восхищён» разрешением ситуации с его гипотезой после стольких десятилетий. У доказательства Шитова «есть определённая элегантность, простота и явное качество», написал он в емейл.
Новый контрпример оказался хитроумным и изобретательным, говорят математики, и ему не нужны сложные передовые математические инструменты. «Специалисту по теории графов эту конструкцию можно объяснить двумя предложениями», — сказал Калай.
Почему этот аргумент никто не замечал более 50 лет — для математиков загадка. «Иногда маленький драгоценный камень прячется под грудой листвы, — сказал Хелл. — Шитову просто удалось понять этот вопрос глубже, чем всем остальным».
Графы Шитова получаются гигантскими: он не подсчитывал их точный размер, но оценивает, что у графа G, вероятно, будет около 4100 вершин, а у экспоненциального — не менее 410000 вершин, то есть куда как больше, чем примерное количество элементарных частиц в наблюдаемой Вселенной [порядка 1080 / прим. перев.].
Но, конечно, всё зависит от наблюдателя. Шитов считает, что его контрпример «не такой уж и огромный. В математике можно найти контрпримеры, по сравнению с которыми этот будет весьма крохотным».
И хотя вы вряд ли сможете пригласить 410000 в ваш загородный дом, работа Шитова не отвергает существования контрпримеров гораздо меньшего размера. Но теперь, когда математики знают, что гипотеза Хедетниеми ложна, естественным вопросом будет, насколько именно она ложна: насколько меньше цветов может понадобиться для раскраски тензорного произведения по сравнению с составляющими его графами, и какое минимальное количество узлов и рёбер может быть у таких контрпримеров?
Тем временем, Элон сказал, что в новой работе содержится важный урок для всех математиков: «Иногда причина того, что гипотезу так сложно доказать, заключается в том, что она ложна».
