Хабрахабр

[Перевод] Российский математик опроверг 53-летнюю гипотезу о раскраске сетей

Всего три страницы потребовалось российскому математику, чтобы описать способ раскраски сетей определённого типа, превзошедший ожидания экспертов

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

хроматическое число / прим. Задачи по раскраске сетей [см. Задача состоит в том, чтобы понять, как раскрашивать узлы некоей сети (или графа, как зовут их математики) так, чтобы у любых двух связанных узлов были разные цвета. перев.], вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет. Даже на поиски ответа на вопрос, с которого началась вся эта область исследований – достаточно ли четырёх цветов для раскраски любой карты? В зависимости от контекста, эта раскраска может предоставить эффективный способ рассадки гостей на свадьбе, расстановке производственных задач по свободным временным промежуткам, или даже решения судоку.
Задачи по раскраске графов часто легко сформулировать, однако невероятно трудно решить. – ушло более ста лет (если вам интересно, то ответ – да).

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

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

«Это одна из основных гипотез в теории графов, — сказал Гил Калай из Еврейского университета в Иерусалиме. В 1966 году Стивен Хедетниеми, сегодня работающий профессором в Университете Клемсона в Южной Каролине, в своей докторской диссертации выдвинул предположение, что минимальное количество цветов, необходимое для раскраски тензорного произведения, равняется наименьшему из двух количеств цветов, необходимых для раскраски любого из двух составляющих его графов. – Её пыталось обдумывать много людей».

У разных математиков были разные предположения по поводу того, какой из вариантов в итоге победит. За прошедшие десятилетия математики собрали гору свидетельств, некоторые из которых говорили об истинности гипотезы, а некоторые – о её ложности. Но все соглашались, что, по крайней мере, это сложная задача.

«Лично я считал, что эта гипотеза верна, поскольку огромное количество умных людей изучали её, и должны были бы придумать контрпример», если бы такой существовал, сказал Энтони Бонато из Университета Райерсона в Торонто.

Доказательство вышло «элементарным, но гениальным», сказал Павол Хелл из университета Саймона Фрейзера в Бёрнаби (Канада). И вот российский математик Ярослав Николаевич Шитов придумал простой способ создания контрпримеров, тензорных произведений, которым требуется меньше цветов, чем любому из двух составляющих их графов.

«Это важнейший прорыв». Тензорные графы тесно связаны с вопросами об отображениях разных графов друг на друга, и в этой области математики гипотеза Хедетниеми была, вероятно, крупнейшей из открытых проблем, сказал Хелл.

Цветастые сборища

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

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


Ярослав Шитов обнаружил контрпример гипотезе Хедетниеми 53-летней давности из теории графов

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

Если вы сможете раскрасить вершины тензорного произведения так, чтобы у соединённых рёбрами вершин были разные цвета, это даст вам способ формирования списков гостей на разные выходные: вы можете пригласить людей, соответствующих зелёным вершинам, в «зелёные» выходные, красным вершинам – в «красные», и так далее, и быть уверенным в том, что несовместимые гости окажутся в списках на разных выходных. У тензорного произведения двух этих графов будут узлы для каждой пары работа-хобби, а две вершины будут объединяться, если как обе работы, так и оба хобби несовместимы – это как раз та ситуация, которой вы хотите избежать на выходных. Количество использованных вами цветов сообщит вам, сколько выходных нужно будет занять в календаре.

Такая раскраска приведёт к тому, что на сборищах каждая пара гостей будет совместима исключительно по профессиональным интересам, вне зависимости от их хобби. Из этого примера следует, что любая допустимая раскраска графа работ переносится и на тензорное произведение – вы можете просто раскрасить каждую комбинацию работа-хобби тем же цветом, что вы использовали и для работы.

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

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

Они смогли доказать, что гипотеза верна, если для раскраски одного из двух графов требовалось не более четырёх цветов. И всё же в течение более чем 50 лет математики не могли найти ни одного тензорного произведения, для раскраски которого требовалось бы меньше цветов, чем для любого из составляющих его графов. (В терминах выходных сборищ это может соответствовать ситуации, когда в вашем списке друзей есть три журналиста, один из которых играет в теннис, и вы пригласили двух из них на «жёлтые» выходные, а третьего – на «зелёные»). Она также верна в более общем случае «дробных» раскрасок, когда каждой вершине можно назначать комбинацию из цветов – например, 2/3 жёлтого и 1/3 зелёного.

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

«Все в целом считали её верной, однако доказать или опровергнуть это было сложно», — сказал Нога Элон из Принстонского университета.

Раскрашивая страницы

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

У экспоненциального графа имеется по одному узлу для каждой из возможных раскрасок G неким фиксированным количеством цветов (разрешаются все возможные раскраски, не только те, у которых соединённые вершины имеют разные цвета). Шитов начинает работу с наблюдения за тем, что произойдёт, если скомбинировать граф G с одним из его экспоненциальных графов, и получить их тензорное произведение. Если у графа G, допустим, 7 вершин, а в нашей палитре 5 цветов, тогда у экспоненциального графа будет 57 вершин – поэтому он и называется экспоненциальным.


Гипотеза Стивена Хедетниеми о минимальном количестве цветов для раскраски тензорного произведения графов оставалась неподтверждённой более 50 лет

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

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

У доказательства Шитова «есть определённая элегантность, простота и явное качество», написал он в емейл. Хедетниеми заявил, что «совершенно восхищён» разрешением ситуации с его гипотезой после стольких десятилетий.

«Специалисту по теории графов эту конструкцию можно объяснить двумя предложениями», — сказал Калай. Новый контрпример оказался хитроумным и изобретательным, говорят математики, и ему не нужны сложные передовые математические инструменты.

«Иногда маленький драгоценный камень прячется под грудой листвы, — сказал Хелл. Почему этот аргумент никто не замечал более 50 лет – для математиков загадка. – Шитову просто удалось понять этот вопрос глубже, чем всем остальным».

перев.]. Графы Шитова получаются гигантскими: он не подсчитывал их точный размер, но оценивает, что у графа G, вероятно, будет около 4100 вершин, а у экспоненциального – не менее 410000 вершин, то есть куда как больше, чем примерное количество элементарных частиц в наблюдаемой Вселенной [порядка 1080 / прим.

Шитов считает, что его контрпример «не такой уж и огромный. Но, конечно, всё зависит от наблюдателя. В математике можно найти контрпримеры, по сравнению с которыми этот будет весьма крохотным».

Но теперь, когда математики знают, что гипотеза Хедетниеми ложна, естественным вопросом будет, насколько именно она ложна: насколько меньше цветов может понадобиться для раскраски тензорного произведения по сравнению с составляющими его графами, и какое минимальное количество узлов и рёбер может быть у таких контрпримеров? И хотя вы вряд ли сможете пригласить 410000 в ваш загородный дом, работа Шитова не отвергает существования контрпримеров гораздо меньшего размера.

Тем временем, Элон сказал, что в новой работе содержится важный урок для всех математиков: «Иногда причина того, что гипотезу так сложно доказать, заключается в том, что она ложна».

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть