[Перевод] Изящное шестистраничное доказательство. Как возникают случайные структуры
Результирует ли случайный граф в треугольник (справа), гамильтонов цикл (в центре) или проявит какие-либо иные интересующие нас свойства?
Двое молодых математиков ошеломили коллег, представив полное доказательство гипотезы Кана-Калаи — обобщающее утверждение о том, как возникает структура в случайных множествах и графах.
Когда математики Джефф Кан и Гиль Калаи в 2006 году впервые выдвинули свою гипотезу о «пороге ожидания», они сами в нее не поверили. Их тезис — широкое утверждение о природе математических объектов, именуемых «случайными графами» — казался слишком категоричным, слишком всеобъемлющим, слишком смелым, чтобы претендовать на истинность. Казалось, что он скорее выдает желаемое за действительное, чем отражает математическую истину. Даже с такими оговорками, никто не смог опровергнуть эту гипотезу, и она быстро стала одной из важнейших нерешенных задач в своей области.
Теперь, более 15 лет спустя, двое молодых математиков из Стэнфордского университета сделали то, что, по мнению Кана и Калаи, граничит с невозможным. В на удивление кратком препринте, выложенном в онлайне всего несколько недель назад, Джинён Пак и Гью Туан Фам дали полное доказательство этой гипотезы.
«Оно получилось поразительно простым и изобретательным», — сказал Калаи, — «Завораживающим. Чудесным».
Полученный результат автоматически доказывает сотни более специфичных утверждений, каждое из которых с большим трудом поддавалось бы доказательству само по себе — и влечет с собой еще более глубокие следствия для нашего понимания случайных графов и математических множеств в более широком смысле.
«Я бы назвал их доказательство волшебным», — сказал Джейкоб Фокс, стэнфордский математик, а также научный руководитель Фама, — «оно продвинет вперед значительную часть всей дисциплины».
Замораживаем граф
Гипотеза Кана-Калаи очень обширна и сформулирована на абстрактном языке множеств и их элементов — но, понять ее можно на достаточно простом примере. Для начала представьте граф: множество точек (вершин), соединенных линиями (ребрами). Чтобы сделать случайный граф, возьмем несимметричную монету — такую, что выпадает решкой в 1% случаев, или 30%, или с любым иным процентным соотношением от 0% до 100% — и подбросим ее единожды для каждой пары вершин. Если монета упадет решкой, соединим эти вершины ребром, если упадет орлом — не соединим. Повторим этот процесс для любых возможных пар вершин.
Джинён Пак, математик из Стэнфордского университета, говорит, что «смогла ощутить красоту и силу этой гипотезы, но и представить не могла бы, что мне удастся ее доказать».
Фото: Род Сирси
Математики заинтересовались, когда такой граф, вероятно, может обладать той или иной интересной структурой. Может быть, в нем образуется треугольник, а может быть — гамильтонов цикл; цепочка ребер, проходящая через каждую из вершин ровно один раз. Можно подумать о любом свойстве, до тех пор, пока оно идет с «нарастанием» — то есть, если при добавлении ребер в граф, уже обладающий данным свойством, данное свойство сохраняется.
Если вероятность падения монеты решкой невелика, то и ребра будут редки, а такие структуры как гамильтонов цикл, вряд ли возникнуть. Но, если удастся настроить вероятность, то произойдет нечто странное. Каждое свойство обладает так называемым «порогом»: уровень вероятности, при котором возникает структура, зачастую — совершенно внезапно.
Точно как ледяные кристаллы начинают формироваться, как только температура упадет ниже нуля по Цельсию, вероятность возникновения некоторого свойства вдруг становится очень высокой по мере того, как все больше ребер добавляется в граф. Когда ребра добавляются в случайный граф с N вершин, с вероятностью, например, менее log (N)/N, в таком графе вряд ли возникнет гамильтонов цикл. Но, стоит откорректировать вероятность так, чтобы она была хотя бы чуточку выше log (N)/N, вероятность возникновения гамильтонова цикла становится крайне высокой.
Математики хотят определять такие пороговые уровни для различных свойств, представляющих интерес. «Возможно, пороги — самая фундаментальная вещь, которую мы пытаемся понять», — говорит Фокс, — «я рассматриваю случайный объект: обладает ли он интересующим меня свойством»? Но, тогда как такие пороговые значения уже вычислены для гамильтоновых циклов и некоторых других конкретных структур, в большинстве случаев по-прежнему очень затруднительно определить такой порог или даже уверенно оценить его.
Поэтому математики зачастую полагаются на более простое вычисление, дающее минимально возможное значение порога, то есть, его нижнюю границу. Этот «порог ожидания» в сущности, вычисляется взятием средневзвешенного значения. «Самое приятное с этим порогом ожидания — в том, что он очень легко выяисляется», — говорит Дэвид Конлон, математик из Калифорнийского технологического института, — «в принципе, всего в двух строках можно рассчитать порог ожидания практически для чего угодно».
Но средние значения бывают обманчивы. Так, для гамильтонова цикла порог ожидания равен 1/N, что гораздо ниже истинного значения log (N)/N, в log (N) раз.
Гиль Калай в Еврейском Университете Иерусалима.
Фото: Дэниэл Ваакнин для Quanta Magazine
В 2006 году Кан и Калаи постулировали, что это, на самом деле, наихудший сценарий. Согласно гипотезе, названной в их честь, разрыв между ожидаемым и истинным пороговым значением никогда не может превышать логарифмического множителя. По Конлону, эта гипотеза «в сущности, берет за основу центральный вопрос, касающийся случайных графов, и предлагает на него общий ответ».
Но это был всего лишь простой случай. Данная гипотеза актуальна далеко не только для случайных графов. Если она верна, то справедлива и для последовательностей случайных чисел, и для обобщений графов — так называемых гиперграфов, и даже для еще более обширных категорий систем. Вот почему Кан и Калаи сформулировали свое утверждение в терминах абстрактных множеств. Случайные графы — это всего лишь частный случай — случайный граф можно трактовать как случайное подмножество от множества всех возможных ребер —, но есть и многочисленные иные объекты, попадающие в область применения этой гипотезы. «Странно, но, работая с графами, доказать ее в таком контексте было бы очень сложно», — говорит Конлон, — «но, именно в такой абстрактной постановке задачи каким-то образом раскрывается суть всей проблемы».
Утверждение Кана-Калаи казалось столь невероятным именно из-за своей всеохватности. «Это была очень смелая гипотеза», — сказал Шахар Ловетт, специалист по теоретической информатике из Калифорнийского университета в Сан-Диего. Во-первых, она мгновенно спрямила огромный фронт работ в комбинаторике — попытки рассчитать пороговые значения для различных свойств. «Вопросы, требовавшие, казалось бы, очень длинных и сложных доказательств, вдруг просто исчезли», — говорит Алан Фриз, математик из университета Карнеги-Меллона. — «Доказательства превратились просто в тривиальные варианты применения этой гипотезы».
Тот факт, что столь многие, казалось бы, несвязанные проблемы, удавалось уладить при помощи такой широкой гипотезы, казался многим математикам натяжкой. «Честно говоря, это казалось полным безумием», — сказал Конлон. Кан и Калаи, сформулировав свою гипотезу, не пытались ее доказать. Они занялись поиском контрпримера. Существовало так много постановок задачи, которые они могли бы исследовать, что, заключили эти ученые, рано или поздно они на такой пример наткнутся.
Но, как оказалось (это слова Калаи), «история стала развиваться по совсем иному сценарию», чем они ожидали.
Путеводный подсолнух
Методы, которые в итоге привели к новому доказательству гипотезы Кана-Калаи, начались с прорыва в решении, казалось бы, совсем иной задачи. Во многом эта история начинается с так называемой «гипотезы подсолнечника», сформулированной математиками Палом Эрдёшем и Рихардом Радо в 1960 году. В рамках этой гипотезы рассматривается, можно ли собирать совокупности множеств по принципу, напоминающему расположение лепестков подсолнуха.
В 2019 году Ловетт работал в составе команды, очень близко подобравшейся к полному решению задачи подсолнечника. На тот момент казалось, что эта работа никак не связана с гипотезой Кана-Калаи, которая оперирует вероятностными рассуждениями. «Я не вижу никакой связи с вашей гипотезой», — сказал Калаи. Не видел такой связи и Ловетт, признавший, что «мы не подозревали о том, что она касается иных вопросов. Нас интересовали подсолнечники».
Но Кан, Пак (на тот момент — докторантка Кана) и их коллеги в итоге смогли связать две эти задачи, когда, несколько месяцев спустя, попытались доказать облегченную версию гипотезы Кана-Калаи. (Их доказательство было опубликовано в журнале Annals of Mathematics в прошлом году). В этой облегченной версии, которую сформулировал французский математик Мишель Талагран, «порог ожидания» из гипотезы Кана-Калаи заменялся «дробным» порогом ожидания — в сущности, применялся иной способ взятия средневзвешенного значения. В пересмотренном определении «появляется больше пространства для маневра при работе», как выразился Ловетт.
Группа, в которой работали Кан и Пак, осознала: можно позаимствовать приемы, позволившие в 2019 году получить результат по гипотезе подсолнечника, скорректировать их и применить к гипотезе Талаграна. «Определенно, это послужило нам толчком», — сказал Кан.
Математики стали решать задачу итерационным методом. Они взялись показать, что, если выбрать случайное множество — скажем, случайный граф — то в нем будет структура, например, гамильтонов цикл. Но они решили выбирать такое случайное множество не сразу, а фрагмент за фрагментом, примерно так, как Ловетт и его коллеги подходили к гипотезе подсолнечника. «Мы итеративно выполняем своеобразный случайный процесс», — говорит Пак, — «пошагово выбираем ребро за ребром». И так, пока в них не соберется полный гамильтонов цикл.
Чтобы добиться этого, команда обратилась к понятию «разброс», характеризующему степень случайности. Если гамильтоновы циклы обладают хорошим «разбросом», это значит, что не так много циклов содержат одно и то же ребро или подмножество ребер. «Каким-то образом набор ребер разбросан в пространстве», — говорит Фам, — «он не демонстрирует особой кластеризации или концентрации в какой-либо части». Если циклы хорошо распределены таким образом, то процесс случайного поэлементного включения гарантированно позволит захватить как минимум один гамильтонов цикл, даже, если многие другие циклы будут при этом упущены.
Такой подход оказался возможен только благодаря критически важной эквивалентности: разброс можно квантифицировать таким способом, который напрямую соотносится с дробным порогом ожидания. Именно поэтому математикам удалось переписать гипотезу Талаграна в терминах разброса.
Занятно, что доказательства этой более слабой гипотезы хватило, чтобы решить целый вихрь задач, связанных с порогами. «Каждое следствие, которое, как нам известно, вытекает из полной гипотезы, также вытекает и из более слабой», — сказал Кан. Фактически, ему, Калаи и другим это подсказывало, что две гипотезы могут быть более или менее одинаковы, то есть, что значения дробных и исходных порогов ожидания были, в сущности, эквивалентны. Если бы кому-нибудь удалось доказать эту эквивалентность, то была бы доказана и гипотеза Кана-Калаи. «Я всегда думал, что единственный способ доказать нашу гипотезу — именно такой», — сказал Кан.
Но произошло нечто другое. Пока другие математики пытались придерживаться именно такого маршрута к полному доказательству гипотезы Калаи-Кана, Пак и Фам нашли совершенно новый подход. «Джинён и Гью нашли эту невероятно прямую, невероятно короткую линию доказательств, которая просто простреливает всю проблему», — сказал Конлон, — «и это экстраординарно. Я такого совершенно не ожидал».
Кан согласен. «Это одна из тех прелестных вещей, какие случаются в математике», — говорит он, — «вещи, казавшиеся нам безнадежными, оказываются не только небезнадежными, но даже несложными».
Удивительный подход
Поначалу ни Пак, ни Фам не планировали браться за исходную гипотезу. Пак, впервые узнавшая об этой задаче в аспирантуре, по ее словам, «смогла почувствовать красоту и силу этой гипотезы, но никогда и не думала, что сможет ее доказать».
«Мы этого совершенно не планировали», — добавляет Фам.
Напротив, они занимались другой гипотезой, сформулированной Талаграном, когда их, по словам Фама, «просто озарило». Они осознали, что «картина, которая здесь открывается перед нами, идеи, которые у нас есть, почему-то должны быть гораздо мощнее, чем кажутся». Эти идеи, рассудили они, вполне помогут пройти весь путь к доказательству гипотезы Кана-Калаи.
Гью Туан Фам
Из личного архива
Всего за одну бессонную мартовскую ночь они сформулировали, как заставить это доказательство работать.
Нормальный порог ожидания, в отличие от дробного, никак не связан с разбросом. Разброс «дает отправную точку. И ты переходишь к исходной, недробной гипотезе, а та отправная точка просто исчезает», — говорит Кан, — «так что все выглядело очень сурово».
«Что же делать в таком случае?», — сказал Фам, — «мы тогда просто взглянули на проблему под другим углом».
В частности, они стали размышлять над этой задачей в терминах математической сущности, именуемой «покрытием». Покрытие — это совокупность множеств, где каждый объект, обладающий определенным свойством, содержит одно из этих множеств. Например, одно из возможных покрытий всех гамильтоновых циклов — это совокупность всех ребер. Каждый гамильтонов цикл будет содержать одно из этих ребер.
Пак и Фам переписали гипотезу Калаи-Кана таким образом, который позволил им работать с покрытиями. В исходной версии гипотезы налагаются ограничения на то, какова должна быть вероятность падения симметричной монеты решкой, чтобы гарантировать, что случайный граф или множество будут содержать некоторое свойство. В частности, в ней говорится, что вероятность должна быть не менее порога ожидания для данного свойства, который умножен на логарифмический коэффициент. Пак и Фам перевернули ситуацию: если возникновение некоторого свойства маловероятно, то вероятность, присвоенная симметричной монете, будет ниже порога ожидания, умноженного на логарифмический коэффициент.
Тут в игру и вступают покрытия: когда для подмножества структур можно собрать небольшое покрытие (скажем, таким подмножеством может быть небольшой набор гамильтоновых циклов), это означает, что вклад данного подмножества в порог ожидания невелик. (Напомню: порог ожидания рассчитывается взятием средневзвешенного значения для всех возможных структур заданного типа). Поэтому, теперь Пак и Фаму требовалось показать, что, если в случайном множестве невелика вероятность присутствия искомой структуры, то для всех таких искомых структур должно существовать небольшое покрытие. Основная часть их доказательства посвящена сборке такого небольшого покрытия.
Они решили задачу при помощи пофрагментного сбора образцов — процесса, уже применявшегося при получении более ранних результатов, а также введя, как выразился Фокс, «очень умный аргумент подсчета». Неделю спустя после той бессонной мартовской ночи, они выложили свою изящную шестистраничную статью в Интернете.
«Их доказательство суперпростое. Они берут базовую идею, разработанную нами, а также идеи из других статей — и добавляют в нее небольшой вираж», — говорит Ловетт, — «и с этим новым виражом все значительно, значительно упрощается».
Фриз того же мнения. «Не могу этого объяснить, но, поразительно, тут все верно», — говорит он.
Гипотеза Кана-Калаи, верность которой уже доказана, точно как и дробный результат, автоматически подразумевает доказательство целой кучи смежных гипотез. Но, более того, «это мощная доказательная техника, которая может привести нас к множеству других вещей», — говорит Нога Эйлон, математик из Принстонского университета, — «главное, что они смогли сделать это как следует».
Пак и Фам уже начали применять свой метод к решению других задач. В частности, они стремятся точнее понять разрыв, отделяющий порог ожидания и реальный порог. Доказав гипотезу Кана-Калаи, они продемонстрировали, что этот разрыв обычно сопоставим с логарифмическим коэффициентом –, но иногда гораздо меньше, а бывает, что его и нет. В настоящее время не существует более широкого механизма, позволившего бы классифицировать, в каких случаях каждый из этих сценариев может быть верен; математикам придется проработать его пример за примером. На данный момент «мы считаем, что, при помощи такой эффективной техники, можно надеяться, что удастся с гораздо более высокой точностью локализовать эти пороги», — говорит Фам.
А еще это доказательство может привести к совершенно иным следствиям. «Ведь гипотеза Кана-Калаи — совершенно не конец истории», — говорит Пак.
