Математики доказали, что копиями графов меньшего размера всегда можно идеально покрыть графы большего размера

8 января трое математиков опубликовали доказательство теоремы из комбинаторики, сформулированной почти 60 лет назад, известной, как гипотеза Рингеля. Грубо говоря, она предсказывает, что графы – конструкции, состоящие из точек и линий – можно идеально сложить из одинаковых частей меньшего размера.

Математики с восторгом приняли подтверждение этой гипотезы.

«Счастье в том, что эта работа решает очень старую гипотезу, которую невозможно было проверить другими методами», — сказал Гил Калай, математик из Еврейского университета в Иерусалиме, не связанный с этой работой.

Гипотеза Рингеля предсказывает, что особые типы сложных графов – с триллионами вершин и рёбер – можно «замостить», т.е. полностью покрыть, отдельными копиями меньших графов определённого типа. С концептуальной точки зрения этот вопрос похож на следующий: могу ли я полностью замостить пол на кухне одинаковыми копиями какой-либо плитки, имеющейся в магазине? В реальной жизни большинство типов плитки не подойдёт для вашей кухни – чтобы полностью покрыть пол, придётся комбинировать их разные формы. Но в мире теории графов гипотеза предсказывает, что замостить граф можно всегда.

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

Лес с деревьями

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

«У вас есть набор кусочков головоломки, и вы не знаете, можно ли её собрать из этих кусочков», — сказал Джейкоб Фокс из Стэнфордского университета.

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

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

Вопрос Рингеля относится к взаимоотношению полных графов и деревьев. Он сказал: сначала представим полный граф из 2n+1 вершин (нечётное число). Затем представим любое дерево, состоящее из n+1 вершин – а такие деревья могут быть очень разными.

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

Рингель предсказал, что действуя подобным образом, и начав в нужном месте, вы сможете идеально замостить весь полный граф. Это значит, что каждое ребро полного графа будет покрыто ребром дерева, и копии деревьев не будут накладываться друг на друга.

«Я могу взять копии дерева. Я кладу одну копию на полный граф. Она покрывает какие-то рёбра. Потом я повторяю процесс. Гипотеза говорит о том, что так можно покрыть всё», — сказал Бенни Судаков из Швейцарского федерального технологического института, соавтор нового доказательства, совместно с Ричардом Монтгомери из Бирмингемского университета и Алексеем Покровским из Биркбекского колледжа при Лондонском университете.

Наконец, Рингель предсказал, что замостить граф можно вне зависимости от того, какое из множества вариантов деревьев вы будете использовать. Такое заявление может показаться слишком общим. Гипотеза Рингеля применима как к полным графам с 11 вершинами, так и к полным графам с 11 триллионами + 1 вершиной. И чем больше будет полный граф, тем сильнее будет расти число возможных деревьев, которые можно нарисовать для n+1 вершин. Как же каждое из них сможет идеально замостить соответствующий полный граф?

Однако были причины полагать, что гипотеза Рингеля может быть верной. Самым первым подтверждением было то, что простейшая комбинаторная арифметика не исключала такого варианта: количество рёбер в полном графе с 2n+1 вершинами всегда можно нацело разделить на количество рёбер в дереве с n+1 вершинами.

«То, что количество рёбер полного графа делится на количество рёбер дерева, очень важно», — сказал Монтгомери.

Математики быстро отыскали ещё одно свидетельство правдоподобности гипотезы, что и запустило цепочку открытий, в итоге приведшую к доказательству.

Размести и поверни

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

И, естественно, математики быстро обнаружили, что звезда из n+1 вершин всегда идеально вымащивает полный граф с 2n+1 вершиной. Такой факт сам по себе интересен, однако его доказательство заставило математиков размышлять дальше.

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

Теперь рассмотрим соответствующую ему звезду: центральную точку с пятью исходящими из неё рёбрами.

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

Будем вращать звезду далее. К тому времени, когда мы вернёмся туда, откуда начали, мы вымостим весь полный граф без наложения звёзд – точно так, как предсказывал Рингель.

«Мы знаем, что гипотезу нельзя отбрасывать сразу, по крайней мере, если мы возьмём дерево в виде звезды, — сказал Судаков. – Более того, мы даже можем очень красиво продемонстрировать это: нанесём граф на окружность, сдвигаем звезду, получаем новые копии, и замещаем весь граф».

Вскоре после того, как Рингель высказал свою гипотезу, словацко-канадский математик Антон Коциг использовал этот пример для ещё более смелого предсказания, чем у Рингеля. Рингель сказал, что каждый полный граф с 2n+1 вершиной можно замостить любым деревом с n+1 вершиной, Коциг предположил, что замостить его можно точно таким же способом, как при помощи звезды: помещая дерево на полный граф и просто поворачивая его.

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

«Звезда была простой структурой, которую можно разместить вручную, однако если у вас на руках раскидистое дерево с кучей ветвей разной длины, сложно представить, как его можно тщательно разместить», — сказал Покровский.

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

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

Представим себе снова полный граф с 11 вершинами, расположенными по окружности. Разметим его рёбра цветовыми кодами по простому правилу, учитывающему расстояние между двумя вершинами.

Это расстояние определяется количеством шагов, которые необходимо сделать, чтобы пройти от одной вершины до другой по окружности (не срезая путь внутри окружности). Конечно, по кругу всегда можно пойти в две стороны, поэтому мы определим расстояние, как кратчайший путь между двумя вершинами. Если это соседние вершины, то расстояние между ними будет 1, а не 10. Если они разделены одной вершиной, то расстояние будет равным 2.

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

Продолжим раскрашивать граф так, чтобы все рёбра, соединяющие вершины, находящиеся на одном расстоянии, имели одинаковый цвет. Разные расстояния будем кодировать разными цветами. На полный граф с 2n+1 вершиной вам потребуется для этого n цветов. В итоге получится красивая и полезная картинка.

Вскоре после того, как Рингель и Коциг высказали свои гипотезы, Коциг понял, что его раскраска полного графа может стать руководством по размещению на нём дерева.

Идея в том, чтобы расположить дерево так, чтобы оно покрывало по одному ребру каждого цвета, и не покрывало ни один цвет дважды. Математики называют такое расположение радужной копией дерева. Поскольку для раскраски требуется n цветов, а у дерева из n+1 вершины будет n рёбер, мы сразу знаем, что с большой вероятностью радужную копию можно будет найти.

К концу 1960-х математики понимали, что у радужной копии дерева есть одно особое свойство: она обозначает как раз то положение, из которого можно, вращая дерево, замостить весь граф.

«Если вы сделаете радужную копию, то всё будет работать», — сказал Покровский.

После этого математики уже знали, что могут доказать гипотезу Рингеля, доказав, что в каждом полном графе с 2n+1 вершиной содержится радужная копия любого дерева с n+1 вершиной. А если радужная копия всегда существует, то всегда можно замостить граф.

Однако доказать, что нечто существует всегда, тяжело. Для этого математикам пришлось бы показать, что полные графы просто не могут не содержа��ь в себе радужных копий деревьев. На это ушло более 40 лет, но именно этого добились Судаков с соавторами в новой работе.

Идеальная упаковка

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

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

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

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

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

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

Представьте себе дерево с 11 рёбрами. Шесть из них сходятся в центральной точке. Почти все остальные образуют единую форму, отстоящую от основной.

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

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

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

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

«К самому концу встраивания деревьев, когда ситуация становится сложной, у меня остаётся не один обязательный цвет, а небольшой выбор», — сказал Монтгомери.

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

«Теперь можно заставить то, что вы отложили с самого начала, как бы впитать то, что осталось от дерева, и получить полную радужную раскраску», — сказал Нога Алон из Принстонского университета.

Математики не описали точного способа нахождения радужной копии для каждого дерева с n+1 вершиной в каждом полном графе с 2n+1 вершинами. Однако они доказали, что радужная копия обязана в нём быть.

А если радужная копия всегда существует, то всегда можно замостить граф предсказанным Рингелем методом. Таким образом, его гипотеза оказывается верной.

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

«Оно показывает, что методы, над которыми люди уже довольно давно размышляют, действительно обладают широкими возможностями, — сказал Фокс. – Если их правильно применить, можно решать такие задачи, которые ранее казались неприступными».

Радужное доказательство демонстрирует наличие стандартных составных частей у графов