Российскому математику потребовалось всего три страницы, чтобы описать метод раскраски сетей определенного типа, превзошедший ожидания специалистов.
Опубликовано в Интернете работа опровергает 53-летнюю гипотезу о наилучшем способе присвоения цветов узлам сети.
В работе всего на трех страницах показано существование методов окраски определенных цветов, превзошедших все ожидания специалистов.
Проблемы с раскраской сети [ см.
хроматическое число / ок.
перевод ], вдохновленные вопросом о раскраске карт, на которых соседние страны имеют разные цвета, были в центре внимания математиков на протяжении почти 200 лет. Задача — понять, как раскрасить узлы определенной сети (или график , как их называют математики), так что любые два соединенных узла имеют разные цвета.
В зависимости от контекста эта раскраска может стать эффективным способом рассадить гостей на свадьбе, распределить производственные задачи по доступным временным интервалам или даже решить судоку .
Задачи по раскраске графов зачастую легко сформулировать, но невероятно сложно решить.
Даже в поисках ответа на вопрос, с которого началась вся эта область исследований - Достаточно ли четырех цветов, чтобы раскрасить любую карту? ? — потребовалось более ста лет (если вам интересно, ответ — да).
Задача, рассматриваемая в новой работе, пока не считается исключением.
Ее не могли решить более 50 лет, и это касается тензорные произведения – графы, состоящие из особой комбинации двух разных графов (назовем их G и H).
Тензорное произведение графов G и H — это новый, более крупный граф, каждая вершина которого обозначает пару вершин исходных графов — одну из G и одну из H — и две вершины тензорного произведения соединены, если обе соответствующие им вершины вершины в G и соответствующие им вершины в H. Допустим, вы учитель музыки и вам нужно найти хорошие пары-дуэты для концерта пятого курса.
Можно создать граф, вершинами которого являются ученики, а связи между парами указывают на наличие между ними хороших отношений.
Затем вы можете создать второй граф, в котором каждый узел представляет отдельный музыкальный инструмент, а связь между ними заключается в том, есть ли у вас ноты для дуэта этих двух инструментов.
В тензорном произведении этих двух графов будет одна вершина для каждой возможной комбинации ученика и инструмента (скажем, Алисы и тромбона), и две вершины будут соединены, если два ученика хорошо работают вместе и два инструмента совместимы.
В 1966 году Стивен Хедетниеми , сегодня профессор Университета Клемсона в Южной Каролине, в своей докторская диссертация выдвигать предположение Минимальное количество цветов, необходимое для окраски тензорного произведения, равно меньшему из двух чисел цветов, необходимых для окраски любого из двух составляющих его графов.
«Это одна из главных гипотез теории графов», — сказал Гил Калаи из Еврейского университета в Иерусалиме.
«Многие люди пытались об этом подумать».
За последние десятилетия математики собрали гору доказательств, часть из которых говорила об истинности гипотезы, а часть — о ее ложности.
У разных математиков были разные предположения о том, какой вариант в конечном итоге выиграет. Но все согласились, что это, по крайней мере, вызов.
«Лично я думал, что эта гипотеза верна, потому что очень много умных людей изучили ее и им пришлось бы придумать контрпример», если бы он существовал, — сказал он.
? Тони Бонато из Университета Райерсона в Торонто.
А вот русский математик Ярослав Николаевич Шитов придумал простой способ создания противоположных примеров — тензорных произведений, для которых требуется меньше цветов, чем для любого из двух составляющих их графов.
Доказательство оказалось «элементарным, но гениальным», сказал он.
Павол Хелл из Университета Саймона Фрейзера в Бернаби (Канада).
Тензорные графы тесно связаны с вопросами об отображении различных графов друг на друга, и в этой области математики гипотеза Хедетниеми была, вероятно, самой крупной открытой проблемой, сказал Хелл.
«Это большой прорыв».
Красочные встречи
Чтобы представить, какую информацию можно извлечь из раскраски тензорного графа, представьте, что вы собираетесь каждые выходные приглашать друзей в свою загородную усадьбу.И, как хороший хозяин, вы хотите собрать вместе людей, которым будет приятно общество друг друга.
Вы знаете, что некоторые из ваших друзей смогут быстро стать друзьями по работе, а другие — нет. Вы также знаете, что у ваших друзей есть хобби – еще один способ для гостей найти общие интересы.
Вы думаете, что учитель танцев, играющий на скрипке, может хорошо проводить время, разговаривая с инструктором йоги, играющим в теннис, или обсуждая музыку с фермером, выращивающим кленовый сироп, играющим на пианино, но ему, вероятно, все равно.
чем поговорить с политологом, который коллекционирует марки.
В любые выходные вы хотите, чтобы каждая пара гостей могла найти какой-то общий интерес, будь то работа или хобби, и вам интересно, сколько встреч вам нужно будет провести, чтобы вместить всех из вашего списка гостей.
.
Ярослав Шитов обнаружил контрпример к гипотезе Хедетниеми 53-летней давности из теории графов
Взаимосвязи между разными видами работ можно представить в виде графа, узлами которого будут произведения, а ребрами будут соединяться любые два произведения, между которыми, скорее всего, не удастся найти общие темы.
для разговора (этот подход может показаться вывернутым наизнанку, но в контексте раскраски графов такое соединение вершин имеет смысл, поскольку мы будем использовать цвета для разделения этих проблемных пар).
Вы также можете составить граф, вершинами которого являются разные хобби, и соединить все несовместимые.
Тензорное произведение этих двух графов будет иметь узлы для каждой пары работа-хобби, и две вершины сольются, если обе работы и оба хобби несовместимы — именно такой ситуации следует избегать на выходных.
Если вы можете раскрасить вершины тензорного произведения так, чтобы вершины, соединенные ребрами, имели разные цвета, это дает вам возможность создавать списки гостей для разных выходных: вы можете приглашать людей, соответствующих зеленым вершинам, на «зеленые» выходные, и люди, соответствующие красным вершинам в «красные» выходные.
» и так далее, и будьте уверены, что несовместимые гости окажутся в списках в разные выходные.
Количество цветов, которые вы используете, подскажет вам, сколько выходных вам понадобится, чтобы заполнить свой календарь.
Из этого примера следует, что любая допустимая раскраска графа работы переносится на тензорное произведение — вы можете просто раскрасить каждую комбинацию работа-хобби тем же цветом, который вы использовали для работы.
Такая расцветка приведет к тому, что на посиделках каждая пара гостей будет совместима исключительно по профессиональным интересам, независимо от их увлечений.
И наоборот, любая допустимая раскраска графа Хобби переносится на тензорное произведение.
Хедетниеми предположил, что лучший способ раскрасить тензорный граф — это раскрасить один из исходных графов минимальным количеством цветов.
На первый взгляд гипотеза Хедетниеми кажется маловероятной.
В конце концов, если вы основываете тензорную раскраску на раскраске рабочего графика, вы игнорируете все, что знаете о совместимых хобби ваших друзей, и потенциально разделяете гостей, которые ладят друг с другом.
Если объединить всю информацию о вашей работе и хобби, возможно, вам удастся использовать меньше цветов и провести заслуженные выходные без гостей.
И все же на протяжении более 50 лет математики не могли найти ни одного тензорного произведения, для раскрашивания которого требовалось бы меньше цветов, чем для любого из составляющих его графов.
Им удалось доказать, что гипотеза верна, если для раскраски одного из двух графов требуется не более четырех цветов.
Это справедливо и в более общем случае дробных раскрасок, когда каждой вершине можно присвоить комбинацию цветов — например, 2/3 желтого и 1/3 зеленого.
(В терминах встреч выходного дня это может соответствовать ситуации, когда в вашем списке друзей есть три журналиста, один из которых играет в теннис, и вы приглашаете двоих из них на желтые выходные, а третьего — на зеленые выходные).
Эти открытия предполагали, что гипотеза может быть верной, но другие говорили обратное.
Например, математики показали, что гипотеза Хедетниеми не работает для графов, для раскрашивания которых требуется бесконечное количество цветов, или для ориентированных графов, ребра которых имеют предпочтительные направления.
Но несмотря на то, что математики доказали гипотезу Хедетниеми для одних случаев и опровергли ее для других, им не удалось решить задачу в той области, которую первоначально рассматривал сам Хедетниеми: конечные неориентированные графы с целочисленной раскраской.
«Все в целом думали, что это правда, но это было трудно доказать или опровергнуть», — сказал Ногалон из Принстонского университета.
Раскраски
Шитов прояснил все эти неясности ясной и простой демонстрацией ошибочности гипотезы Хедетниеми.В статье, основное доказательство которой умещается на одной странице, наполненной математикой, он показывает, как создать особый тип тензорного произведения, для окраски которого требуется меньше цветов, чем для любой из его составляющих.
Шитов начинает свою работу с наблюдения, что произойдет, если он объединит граф G с одним из его экспоненциальных графов, чтобы получить их тензорное произведение.
Экспоненциальный граф имеет по одному узлу для каждой из возможных раскрасок G с определенным фиксированным числом цветов (допускаются все возможные раскраски, а не только те, чьи соединенные вершины имеют разные цвета).
Если граф G имеет, скажем, 7 вершин, а в нашей палитре 5 цветов, то экспоненциальный граф будет иметь 5 7 вершин - поэтому он называется экспоненциальным.
Гипотеза Стивена Хедетниеми о минимальном количестве цветов для раскраски тензорного произведения графов оставалась неподтвержденной более 50 лет.
Если мы вернемся к варианту раскраски, при котором соединенные вершины должны быть разных цветов, то у нас не будет гарантии, что пяти цветов нашей палитры будет достаточно для раскраски графа G, и точно так же их может не быть.
достаточно, чтобы раскрасить экспоненциальный график 5 7 Пики Однако математикам давно известно, что существует один граф, для раскраски которого нужно всего пять цветов: тензорное произведение, состоящее из G и его экспоненциального графа.
Фактически, этим свойством обладают все экспоненциальные графы: тензорное произведение, объединяющее экспоненциальный граф с графом, из которого он был создан, может быть раскрашено точно в то же количество цветов, что и исходный граф.
Шитов опроверг гипотезу Хедетниеми, показав, как можно создать граф G такой, что для раскраски его и его экспоненциального графа потребуется больше цветов.
Хедетниеми сказал, что он «абсолютно рад» тому, что его гипотеза была решена спустя столько десятилетий.
Доказательство Шитова «обладает определенной элегантностью, простотой и очевидным качеством», — написал он в электронном письме.
Математики говорят, что новый контрпример умный и изобретательный и не требует сложных математических инструментов.
«Теоретику графов эту конструкцию можно объяснить в двух предложениях», — сказал Калаи.
Почему никто не заметил этого аргумента более 50 лет, остается загадкой для математиков.
«Иногда под кучей листьев спрятан маленький драгоценный камень», — сказал Хелл.
«Шитов просто сумел глубже всех разобраться в этом вопросе».
Графы Шитова оказываются гигантскими: он не рассчитал их точный размер, но подсчитал, что в графе G, вероятно, будет около 4 100 вершин, а экспоненциальный имеет не менее 4 10000 вершин, то есть гораздо больше, чем приблизительное число элементарных частиц в наблюдаемой Вселенной [ около 10 80 / ок.
перевод ].
Но, конечно, все зависит от наблюдателя.
Шитов считает, что его контрпример «не такой уж и огромный.
В математике можно найти контрпримеры, по сравнению с которыми этот будет совсем крошечным».
И хотя вы вряд ли сможете пригласить 4 10000 в ваш загородный дом, работа Шитова не отрицает существования гораздо меньших контрпримеров.
Но теперь, когда математики знают, что гипотеза Хедетниеми ложна, возникает естественный вопрос: насколько она ложна: насколько меньше цветов может потребоваться для раскраски тензорного произведения по сравнению с составляющими его графами, и каково минимальное количество узлов и ребер, которые такие контрпримеры могли бы быть? Тем временем Лондон заявил, что новая работа содержит важный урок для всех математиков: «Иногда гипотезу так трудно доказать, потому что она ложна».
Теги: #Популярная наука #математика #графы #теория графов #гипотеза Хедетниеми #хроматические числа
-
Принцип Ли
19 Oct, 24 -
Как Лгать, Используя Статистику
19 Oct, 24 -
Обзор Диска Ubuntu 10.04
19 Oct, 24 -
Обзор Предложений Coursera И Edx
19 Oct, 24 -
Он
19 Oct, 24
