Абелевская премия — 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“).

Абелевская премия — одна из самых престижных профессиональных наград для математиков, которым, как известно Нобелевская премия не положена. Ее иногда даже называют «Нобелевской премией для математиков» — такое сравнение оправдано не только размером самой премии (лауреаты 2021 года поделят 7,5 млн норвежских крон, это примерно 735 тысяч евро), но и солидной репутацией, подкрепленной именами тех, кто удостоился премии за без малого 20 лет, которые она вручается. Все без исключения лауреаты — выдающиеся ученые, внесшие существенный вклад в те области математики, которыми они занимаются (список лауреатов можно найти на сайте Абелевской премии, там же есть популярные тексты, объясняющие выбор комитета премии).

Несмотря на то, что первая Абелевская премия была вручена в 2003 году (первым лауреатом стал французский математик Жан-Пьер Серр), ее история началась на рубеже XIX и XX веков. Впервые мысль о необходимости премии для математиков высказал норвежец Софус Ли в 1899 году. Тогда уже шла подготовка к 100-летию со дня рождения Нильса Хенрика Абеля (1802–1829). За свою недолгую и непростую жизнь, которая прервалась из-за туберкулеза, Абель успел сделать очень многое, по сути, заложив основы ряда разделов современной математики. Достаточно упомянуть теорему о неразрешимости в радикалах полиномиальных уравнений степени 5 и выше. Ли узнал, что Альфред Нобель не включил математику в число дисциплин, по которым должны будут присуждаться премии, ныне носящие его имя, и предложил учредить отдельную — чисто математическую — премию. Идея получила поддержку короля Швеции и Норвегии (которые в то время были единым государством) Оскара II и научного сообщества. Но после смерти Ли в том же 1899 году процесс учреждения премии замедлился. В итоге к 1902 году ничего готово не было, а после обретения Норвегией независимости в 1905 году (см. Карлстадские соглашения) к этому вопросу уже не возвращались.

Лауреатами этого года стали венгр Ласло Ловас (L?szl? Lov?sz) и израильтянин Ави Вигдерсон (Avi Wigderson). Если сформулировать в максимально общих терминах, то их результаты относятся к дискретной математике и тому, что раньше называли словом «информатика», а сейчас обычно говорят computer science. Вигдерсон внес важнейший вклад в теорию сложности вычислений, теорию графов, методы распределенных вычислений и концепцию доказательств с нулевым разглашением (суть которой, если сильно упростить, заключается в решении следующей проблемы: как вам убедить кого-то еще в том, что вы умеете решать сложную задачу, но при этом не «засветить» решение или ответ?). Все эти области науки на стыке математики и программирования имеют многочисленные приложения, поэтому вклад Вигдерсона сложно переоценить. О заслугах Ласло Ловаса мы попросили рассказать одного из ведущих российских специалистов по комбинаторике и дискретной математике, профессора МФТИ и МГУ, директора Физтех-школы прикладной математики и информатики и Кавказского математического центра Андрея Райгородского.

Несколько слов о биографии

Я не считаю себя большим знатоком жизни Ласло Ловаса. Я много знаю о его науке, и именно о ней я постараюсь рассказать ниже. Вообще, я очень люблю о ней рассказывать и делаю это регулярно в самых разных аудиториях — школьных, студенческих, очно и дистанционно. Только в этом семестре (весна 2021 года) я прочитал курс лекций в школе «Комбинаторика и алгоритмы» про локальную лемму Ловаса, а также доказывал теоремы Ловаса в курсе комбинаторики у магистрантов Физтех-школы прикладной математики и информатики (ФПМИ) и в курсе дискретного анализа у второкурсников ФПМИ.

Вот небольшой «курикулюм». Ласло Ловас (L?szl? Lov?sz) родился 9 марта 1948 года в Будапеште (Венгрия). С юности он очень ярко проявлял себя в математике. Так, он трижды становился победителем на международных математических олимпиадах (золотая медаль в 1964, 1965 и 1966 годах). Это очень редкое достижение для школьника. Окончил Ловас Будапештский университет, а в 1970 году получил степень кандидата наук в Венгерской академии наук под руководством Тибора Галлаи (Tibor Gallai). Долгие годы он работал в лучших университетах мира, а также сотрудничал с исследовательским центром компании Microsoft до 2006 года. Сейчас он является профессором Института математики Будапештского университета (а в 2006–2011 годах был его директором). С 2014 по 2020 год Ловас также был президентом Венгерской академии наук.

До сих пор Ласло Ловас исключительно активен как ученый. И он действительно внес уже настолько большой вклад в развитие комбинаторики и, более широко, дискретной математики и computer science, что с вердиктом жюри Абелевской премии невозможно не согласиться. Вообще, тот факт, что Абелевские премии стали выдавать «комбинаторщикам», свидетельствует о том, насколько эта наука оказалась «в центре вселенной». Работа Ловаса позволила превратить дискретную математику в одну из центральных самостоятельных дисциплин наравне с алгеброй и геометрией. Для меня лично это важно и как для специалиста в этой области, и как для организатора математики и информатики на Физтехе и в Адыгее, и как для популяризатора комбинаторики.

Ниже я постараюсь рассказать о нескольких направлениях исследований, которые возникли или вышли на новый уровень благодаря Ловасу.

Что такое граф?

Вот именно не «кто такой граф?», а «что такое граф?» Дело в том, что граф — это не только титул, но и математический объект. Значение этого понятия как для самой математики, так и для ее приложений трудно переоценить. Что ж, попробуем разобраться.

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

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

Или вот еще классическая задача про графы. Есть карта мира. Хочется так ее покрасить, чтобы каждая страна была покрашена целиком в один какой-то цвет, а страны, имеющие общую границу, имели разные цвета (не сливались на карте). При этом если страны не граничат между собой, то разрешается красить их в один и тот же цвет. Спрашивается, каким наименьшим количеством цветов можно обойтись? Тут вершины графа — страны (можно, например, отметить точкой столицу страны), а ребра проводятся между парами стран, которые имеют общие границы.

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

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

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

Рис. 1. Слева — полный граф на пяти вершинах: каждая из них соединена ребрами с остальными. На рисунке ребра пересекаются и в точках, отличных от вершин, — это «артефакт», возникающий из-за того, что мы изображаем этот граф на плоскости (кстати, не существует способа сделать это без таких «лишних» пересечений: этот граф не является планарным; более того, в некотором смысле это один из двух «базовых» непланарных графов). Справа — цикл на пяти вершинах. Чтобы его правильно раскрасить, требуется три цвета, поэтому его хроматическое число равно 3

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

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

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

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

Рис. 2. Веретено Мозера. Слева — реализация без самопересечений. Справа — этот же граф, нарисованный так, чтобы все ребра имели одинаковую длину. Такая реализация играет важную роль в задаче о хроматическом числе плоскости

Сама по себе задачка про веретено не висит в воздухе. Она имеет прямое отношение к известной проблеме отыскания хроматического числа плоскости. Желающие могут посмотреть брошюру Хроматические числа (в 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}): он состоит из отдельных ребер, не имеющих общих вершин. К сожалению или к счастью, в общем случае кнезеровские графы устроены очень сложно.

Рис. 3. Примеры кнезеровских графов: (KG_{5,2}) (граф Петерсена), (KG_{5,1}) (полный граф на пяти вершинах), (KG_{6,3}) (набор из десяти несвязных ребер)

Почему кнезеровские графы имеют отношение к кодированию? Пусть, для примера, (n = 5), (r = 2). Посмотрим на вершины графа немного иначе. А именно, каждой из них поставим в соответствие последовательность из пяти нулей и единиц, в которой две единицы стоят на позициях с номерами из данного множества: ( {1,2} ightarrow 11000 ), ( {3,5} ightarrow 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), то нетрудно видеть, что «случится хотя бы одно из событий» — это, визуально, объединение соответствующих областей. Тогда вероятность, интересующая нас, не больше суммы вероятностей отдельных событий (областей), и вот уже про сумму надо доказать, что она строго меньше единицы.

Рис. 4. Примеры событий, которые могут произойти при одном броске игральной кости

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

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

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