Абелевская премия — 2021

17 марта Норвежская академия наук объявила лауреатов Абелевской премии за 2021 год. Эту премию, названную в честь норвежского математика XIX века Нильса Хенрика Абеля, можно считать аналогом Нобелевской премии для математиков — обе награды вполне сравнимы как по престижности, так и по денежному вознаграждению: новоиспеченные лауреаты разделят приз в 7,5 млн норвежских крон. Как отмечается в официальной формулировке, венгерский математик Ласло Ловас и его израильский коллега Ави Вигдерсон отмечены «за фундаментальный вклад в теоретическую информатику и дискретную математику и ведущую роль в их становлении как центральных направлений современной математики» („for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics“).

Читатель может даже попробовать сам доказать такое утверждение: хроматическое число графа не больше двух тогда и только тогда, когда в нем нет циклов нечетной длины. Кому-то это будет легко, а кому-то — не очень. Если есть желание во все это углубиться, то можно послушать мои курсы на Coursera. Но это, конечно, не обязательно. Главное — почувствовать, что хроматическое число — важная характеристика графа и что в общем случае задача его вычисления крайне непростая.

В следующих двух разделах я расскажу о двух выдающихся достижениях Ласло Ловаса, которые связаны с хроматическими числами графов.

Большое хроматическое число и короткие циклы

Мы видели, что у полного графа хроматическое число равно числу вершин. Понятно, что если в графе есть часть, которая сама представляет собой полный граф на (k) вершинах для некоторого (k), то уже на ее покраску нужно (k) цветов, а значит, на весь граф уйдет не менее (k) красок. Например, на рис. 2 изображено так называемое веретено Мозера. В нем целых четыре треугольника, каждый из которых в два цвета, конечно, не красится. Следовательно, хроматическое число веретена не меньше 3. Однако все куда интереснее, и несложно увидеть, что и трех цветов не хватает. В итоге хроматическое число веретена оказывается равным четырем.

Сама по себе задачка про веретено не висит в воздухе. Она имеет прямое отношение к известной проблеме отыскания хроматического числа плоскости. Желающие могут посмотреть брошюру Хроматические числа (в 2015 году вышло второе издание) и статью Прорыв в задаче о раскраске плоскости. Но сейчас особенно важно то, что в веретене нет ни одного полного подграфа на четырех вершинах и, тем не менее, веретено в 3 цвета не красится!

Отсюда сразу возникает такой вопрос: а вообще, нужны ли полные подграфы в графе (а ими являются и треугольники), чтобы его хроматическое число оказалось большим? Ответ на этот вопрос пролил бы свет на то, насколько сложной является в общем случае задача о раскраске. Этот вопрос был поставлен еще в 40-е годы ХХ века. Долгое время математики знали лишь некоторые частные примеры, но полного ответа не было. Наконец, в 1957 году выдающийся комбинаторщик ХХ века Пал Эрдёш доказал следующую совершенно удивительную, на первый взгляд, теорему: пусть даны произвольные (возможно, огромные) числа (k) и (l); тогда найдется граф (возможно, гигантский), у которого хроматическое число больше (k) и у которого в то же время нет ни одного цикла длины (l) или короче.

Чтобы читателю было легче прочувствовать пафос теоремы, возьмем сперва (k = 3), (l = 3). Тогда теорема утверждает, что существует граф с хроматическим числом, не меньшим четверки, и без треугольников (циклов на трех вершинах). Иными словами, этот граф, как и мозеровское веретено, в три цвета не красится, но, в отличие от веретена, даже треугольников не содержит. Но и это не все. Возьмем теперь (k = 10000), (l = 10000). Оказывается, согласно теореме Эрдёша, существует граф, который не содержит ни треугольников, ни четырехугольников, ни пятиугольников, ни… 10 000-угольников и который, однако же, не красится аж в 10 000 цветов! Этот граф, так сказать, ужасающе дырявый, ведь в нем совсем нет коротких циклов, но это не мешает ему крайне туго поддаваться раскраске.

Если читатель еще жив, то он спросит «Как такое возможно? Как нарисовать такой граф?» — и будет совершенно прав. Удивительно, но Эрдёш ничего не рисовал. Он использовал так называемый вероятностный метод в комбинаторике. Грубо говоря, идея следующая. Рассмотрим множество всех графов. Каждому графу присвоим некоторое число — его вес или вероятность. Сумма всех чисел равна единице. Как присвоим, по какому правилу? Здесь не объяснить — всё достаточно хитро. С помощью тонкой математики докажем, что сумма чисел, отвечающих графам, которые нас интересуют (в данном случае нас интересуют графы с большим хроматическим числом и большими «дырками»), положительна. Но раз сумма положительна, то найдется хотя бы один интересующий нас граф! Идея исключительно красивая, и в том числе благодаря Эрдёшу ее стали использовать для доказательства очень многих глубоких фактов в различных областях математики. В качестве литературы здесь я бы предложил ряд брошюр и книг по вероятностному методу и случайным графам (см. брошюры Вероятность и алгебра в комбинаторике (вышло уже третье издание), Модели случайных графов и книгу Н. Алона и Дж. Спенсера Вероятностный метод), а также мою статью Графы с большим хроматическим числом и большим обхватом, в которой доказывается теорема Эрдёша. Но все эти тексты требуют определенной предварительной подготовки. Возможно, и тут сперва будет полезно послушать курсы на Coursera, которые я уже упоминал.

Вроде бы все круто, но, тем не менее, некоторый «осадочек» остается. Мало ли, что там существует! А как бы все же это нарисовать? Или хотя бы описать процедуру рисования? Попробуйте самостоятельно нарисовать что-нибудь в случае (k = l = 3), и вам уже станет грустно с высокой вероятностью. А что делать, когда (k = l = 10000)?! В общем, десять лет никто не мог ничего придумать, покуда к работе над задачей не подключился Ласло Ловас. Именно он, будучи тогда совсем молодым человеком, в конце 60-х годов ХХ века придумал первую процедуру рисования графа с любыми наперед заданными (k) и (l) (L. Lovász, 1968. On chromatic number of finite set-systems). Описать в этой заметке конструкцию Ловаса не представляется возможным — она весьма трудная. Но это был настоящий прорыв, и с этого во многом началась блестящая карьера Ловаса.

Кнезеровские графы

Еще один важнейший, в том числе для приложений в теории кодирования, класс графов был предложен в 50-е годы ХХ века Мартином Кнезером (Martin Kneser). Дадим формальное определение. Пусть (n) — некоторое натуральное число, а (r) — такое натуральное число, что (2 r le n). Рассмотрим все возможные (r)-элементные подмножества множества ({1, ldots, n}). Например, если (n = 5) и (r = 2), то таких подмножеств десять: ({1,2}), ({1,3}), ({1,4}), ({1,5}), ({2,3}), ({2,4}), ({2,5}), ({3,4}), ({3,5}), ({4,5}). Сопоставим вершину графа каждому из этих подмножеств, а ребром соединим два подмножества, если у них нет общих элементов. Такой граф называется кнезеровским и обозначается (KG_{n,r}). На рис. 3 слева изображен граф (KG_{5,2}). Этот частный случай кнезеровского графа также известен в науке под именем графа Петерсена. Граф (KG_{5,1}) — это просто полный граф на пяти вершинах (в середине на рис. 3). А справа на рис. 3 изображен граф (KG_{6,3}): он состоит из отдельных ребер, не имеющих общих вершин. К сожалению или к счастью, в общем случае кнезеровские графы устроены очень сложно.

Почему кнезеровские графы имеют отношение к кодированию? Пусть, для примера, (n = 5), (r = 2). Посмотрим на вершины графа немного иначе. А именно, каждой из них поставим в соответствие последовательность из пяти нулей и единиц, в которой две единицы стоят на позициях с номерами из данного множества: ( {1,2} rightarrow 11000 ), ( {3,5} rightarrow 00101) и так далее.

Эти последовательности, бит за битом, можно передавать по каналу связи, кодируя, тем самым, те или иные слова русского (скажем) языка. Если множества, по которым построены последовательности, не пересекаются, то есть образуют ребро кнезеровского графа, то при передаче соответствующих последовательностей из нулей и единиц можно допустить наличие одной помехи на каждую последовательность. Под помехой мы понимаем ситуацию, когда 0 превращается в 1 или наоборот. В самом деле, пусть слово «мама» закодировано последовательностью 11000, а слово «папа» — последовательностью 00011. Очевидно, что если при передаче этих слов на каждом из них происходит не более одной помехи, то сторона, принимающая сообщение, легко поймет, что именно передавалось — «мама» или «папа». Дело в том, что последовательность 11000 могла превратиться в одну из последовательностей 01000, 10000, 11100, 11010, 11001, но ни одна из них не может быть получена только одной помехой при передаче последовательности 00011. В случае более общих параметров (n) и (r) можно допустить и гораздо большее число помех на канале связи!

Кнезер высказал важную гипотезу о том, что хроматическое число кнезеровского графа равно (n- 2r + 2). Отмечу, что на простых примерах, приведенных выше, гипотеза отлично подтверждается. Например, у полного графа на (n) вершинах хроматическое число равно (n), и это как раз случай (r = 1). А при (r = n/2) всегда получаются отдельно стоящие ребра, и такой граф как раз красится в два цвета.

Поразительно, но гипотеза продержалась два десятка лет, и никакие комбинаторные методы для ее подтверждения или опровержения не срабатывали. В 1978 году Ловас опубликовал работу Kneser’s conjecture, chromatic number, and homotopy, в которой он доказал гипотезу с помощью… топологического метода! Совершенно неожиданные связи бывают в математике, и именно в том величие Ловаса, что он нашел множество таких связей для комбинаторики, сделав в итоге комбинаторику самостоятельной мощной наукой. Подчеркну еще, что пионерская идея Ловаса не просто помогла решить конкретную задачу. Она породила целое направление в комбинаторике, которое долгие годы активно развивается. Разумеется, описание метода Ловаса выходит за рамки этой заметки. Подготовленному читателю можно обратиться, например, к брошюре Гипотеза Кнезера и топологические методы в комбинаторике.

И еще о разных результатах

Еще одним из выдающихся открытий Ловаса стала так называемая локальная лемма (P. Erdős, L. Lovász, 1974. Problems and results on 3-chromatic Hypergraphs and some related questions). Ее довольно трудно объяснить на пальцах. Поэтому я скажу здесь лишь несколько слов о ней. Тем не менее, это один из самых заметных результатов Ловаса, который применяется и в дискретной математике, и в теории чисел, и в других областях науки. Лемма эта — а на самом деле, это мощная самостоятельная теорема — находится в русле вероятностного метода, о котором я писал выше. Грубо говоря, речь вот о чем.

Пусть имеется некоторый набор событий, как-то связанных друг с другом. Например, если бросается игральная кость, то события могут быть такими: «кость выпала четной стороной кверху», «кость выпала четверкой кверху» и так далее. Зачастую важно показать, что с положительной вероятностью ни одно из указанных событий не случится. Как проще всего действовать? Можно заметить, что утверждение «с положительной вероятностью ни одно из событий не случится» равносильно утверждению «с вероятностью, строго меньшей единицы, случится хотя бы одно из этих событий». Если условно изобразить события в виде областей на плоскости (как на рис. 4), то нетрудно видеть, что «случится хотя бы одно из событий» — это, визуально, объединение соответствующих областей. Тогда вероятность, интересующая нас, не больше суммы вероятностей отдельных событий (областей), и вот уже про сумму надо доказать, что она строго меньше единицы.

Однако если событий очень много, то такая грубая оценка может превзойти единицу. Но это нелепо, ведь любая вероятность не больше одного! Так вот локальная лемма — это мощное утверждение о том, что если в некотором смысле каждое событие зависит от не слишком большого числа других событий, то не важно, сколько событий всего, важно только количество этих «локальных» зависимостей. Именно оно в итоге отвечает за то, что вероятность объединения кругов окажется строго меньше одного. Здесь, наверное, можно предложить почитать уже упоминавшиеся брошюру Вероятность и алгебра в комбинаторике и книгу Вероятностный метод.

В завершение скажу еще об одном современном направлении в дискретной математике, которое Ловас также поднял на новый уровень. Речь идет о математике так называемых сложных сетей. На практике это Интернет, социальные сети, сети межбанковских взаимодействий, биологические сети и так далее. С точки зрения математики, оказывается, что такие сети в процессе своего роста обладают определенными устойчивыми свойствами. Например, они достаточно разреженные (число ребер имеет тот же порядок роста, что и число вершин). Во всех них наблюдается «закон» шести рукопожатий (между любыми двумя вершинами есть короткие реберные цепочки). Есть и другие, более хитрые, наблюдения. Подробности этой увлекательной науки можно посмотреть в книге Модели интернета. Одним из направлений в этой науке является создание теории «графовых пределов». Подобно тому, как последовательности чисел могут иметь некоторые предельные значения, у последовательности графов также может быть некоторый предел. Именно в нем содержится информация о тех устойчивых свойствах, которые мы наблюдаем в природе. Ласло Ловас — один из мировых лидеров в этой науке.

Андрей Райгородский

Источник: elementy.ru

голос

Рейтинг статьи

. .