какую премию дают математикам вместо нобелевской
Почему не дают Нобелевскую премию по математике? Какие существуют альтернативы в области математики и других «обделенных» Нобелем наук?
Список направлений, за достижения в которых присуждаются премии, Альфред Нобель явным образом перечислил в своем завещании, которое написал в 1895 году. В этот список попали физика, химия, физиология и медицина и литература. Также, по задумке шведского изобретателя и филантропа, отдельная премия должна была вручаться тому, кто поспособствовал сплочению наций, уничтожению рабства и снижению численности армий. Включение в завещание тех или иных областей было полностью продиктовано личными интересами Нобеля и, кроме математики, в него также не вошли, например, геология, география, биология (за исключением физиологии) или другие виды искусства помимо литературы.
Возможные причины невключения тех или иных областей в список, обозначенный Нобелем в своем завещании, вызывал многочисленные споры. Больше всего обсуждений связано именно с отсутствием в завещании математики, премию по которой Нобель сначала внес в список, а потом заменил ее премией мира. По официальной версии Нобелевского фонда, математика «просто не входила сферу интересов Нобеля», однако существует ряд легенд, которые связывают эту замену с личными отношениями Нобеля с конкретными математиками конца XIX века. В большинстве из этих историй фигурирует шведский математик Магнус Густав Миттаг-Леффлер, который то ли ухаживал за невестой Нобеля, то ли выпрашивал у него пожертвования для своего университета. Тем не менее, никакого документального подтверждения эти рассказы не имеют.
Сейчас как для математиков, так и для представителей других областей науки и искусства, которые Нобель своим вниманием обделил, существуют аналогичные премии, которые сравнительно близки или по статусу и размеру к Нобелевской. У математиков это, в первую очередь, Абелевская и Филдсовская премии, первая из которых вручается с 2002 года ежегодно, а вторая – с 1936 года, но раз в четыре года и только ученым не старше сорока лет. В 1991 году был учреждена премия Вотрена Люда, которую считают аналогом Нобелевской премии в области географии. С 1966 года ежегодно вручается премия Тьюринга по информатике, размер которой близок к размеру премий, вручаемых Нобелевским комитетом.
Аналогичные премии, близкие по статусу к Нобелевской, существуют и в искусстве. Например, архитекторам с 1979 года вручается Притцкеровская премия премия, а музыкантам, композиторам и музыковедам с 1974 года ежегодно присуждают премию Эрнста фон Сименса.
Абелевская премия присуждена за открытие связи между теорией чисел и теорией представлений
Норвежская академия наук объявила лауреата Абелевской премии 2018 года. Им стал канадский математик Роберт Ленглендс. Премия присуждена «за дальновидную программу, соединяющую теорию представлений и теорию чисел».
Абелевскую премию часто называют «Нобелевской премией по математике». В отличие от, например, Филдсовской медали она вручается каждый год. Размер премии — 6 миллионов крон (около 45 миллионов рублей). Церемония награждения пройдет 22 мая 2018 года в Университете Аула, Осло. Вручать награду будет лично король Норвегии Харальд V.
Роберт Ленглендс получил степень PhD в Йельском университете в 1960 году. С 1972 года математик работал в Принстоне — в Институте перспективных исследований. Премия Ленглендсу присуждена за работы, которые ученый сделал 50 лет назад, в 1967 году. Роберт Ленглендс разработал теорию, которая позволяет совершенно по-новому взглянуть на математику: она указала на глубокие связи, лежащие между двумя разными областями математики: теорией чисел и теорией представлений.
Теория чисел изучает целые числа и различные сходные с ними объекты. Например, исследование простых чисел и диофантовых уравнений относится к области теории чисел. Теория представлений работает с абстрактными алгебраическими объектами, например группами симметрий.
Программа Ленглендса стала новым инструментом для работы с математическими утверждениями. Например, с ее помощью была доказана Великая теорема Ферма.
В прошлом году лауреатом Абелевской премии стал французский математик Ив Мейер, сыгравший «ключевую роль в развитии математической теории вейвлетов». Вейвлеты, или как их еще называют всплески, — специальные математические объекты, использующиеся в обработке шумных данных, удалении шумов, хранении и сжатии данных и многих других областях. Например, без вейвлетов не был бы возможен алгоритм JPEG2000. Подробнее об этом можно прочитать в нашем интервью с доктором физико-математических наук Владимиром Юрьевичем Протасовым «Всплеск, который быстро затухает».
Годом ранее Абелевская премия была присуждена Эндрю Уайлсу за доказательство Великой теоремы Ферма — задачи с более чем 350-летней историей. Она утверждает, что для всех возможных натуральных n строго больших двух уравнение x n + y n = z n неразрешимо в целых ненулевых числах. Несколько любопытных историй о Великой теореме Ферма можно прочесть в нашем материале «Кому поля не жмут».
Абелевскую премию вручили ученым, объединившим математику и информатику. Главное
Ави Вигдерсон и Ласло Ловас, которые первыми в своих исследованиях связали математику и информатику, получили за свою работу по разработке теории сложности и теории графов соответственно, а также за соединение этих двух областей премию Абеля в 2021 году. Рассказываем, почему эта работа важна и историю премии Абеля — Моцарта математики с трагичной судьбой.
Читайте «Хайтек» в
Что такое Абелевская премия?
Премия Абеля — премия по математике, названная так в честь норвежского математика Нильса Хенрика Абеля. С 2003 года ежегодно присуждается выдающимся математикам современности в память о выдающемся норвежском математике XIX века Нильсе Хенрике Абеле. Мемориальный фонд Нильса Хенрика Абеля был учрежден 1 января 2002 года и находится в ведении Министерства образования и науки Норвегии.
Основная цель фонда — присуждение международной премии за «выдающуюся научную работу в области математики». Премия также призвана помочь поднять статус математики в обществе и стимулировать интерес молодежи к математике. Ответственность за получение Премии Абеля и за другое использование средств лежит на Норвежской академии наук и литературы. Фонд также поддерживает один или два симпозиума Абеля в год по различным разделам математики, а в 2005 году фонд создал Мемориальный приз Бернта Майкла Холмбо за поощрение передового опыта в преподавании математики.
Джон Нэш, лауреат 2015 года, стал первым человеком, получившим и Абелевскую, и Нобелевскую премии, а в 2019 году награда впервые была присуждена женщине — Карен Уленбек. Русский математик Яков Синай получил Абелевскую премию в 2014 году, а в 2020-м ее получил Григорий Маргулис.
Когда в 1902 году приближалось 100-летие со дня рождения Абеля, планы по созданию премии имени Абеля продвигались норвежским математиком Софусом Ли, но он умер в 1899 году, и идея вместе с ним. Планы по учреждению премии возродились в 1902 году королем Оскаром II, который во время своего правления организовал множество премий. В том числе премию 1880-х годов по небесной механике, которую выиграл французский математик Анри Пуанкаре. Распад союза между Швецией и Норвегией, и, как следствие, потеря доходов положили конец усилиям по учреждению ежегодной премии по математике. Однако статус Абеля в Норвегии оставался высоким, и, когда планы присуждения премии возобновились в 2000 году, который Международный математический союз объявил Всемирным математическим годом, не было сомнений в чью честь её учредить.
Почему Абель — великий математик?
Абель учился самостоятельно, и весной 1823 года он дебютировал в науке, опубликовав статью в первом научном журнале страны, Magazine for Natural Sciences (Magazin for Naturvidenskaberne).
За всю свою короткую жизнь он так и не смог получить постоянную исследовательскую или преподавательскую должность. Живя рука об руку за счет стипендий, временных преподавательских должностей и различных покровителей, в момент своей смерти он работал, чтобы выплатить долги своей семьи в крайней нищете. По крайней жестокой иронии, не прошло и двух дней после его смерти, как пришло письмо от Августа Крелля (из журнала Crelle’s Journal ), в котором сообщалось, что он был назначен профессором Берлинского университета.
Кто получил премию Абеля в этом году?
Одна из самых больших премий по математике была присуждена двум людям за их «фундаментальный вклад в теоретическую информатику и дискретную математику». Ласло Ловас из Института математики Альфреда Реньи в Будапеште, Венгрия, и Ави Вигдерсон из Института перспективных исследований в Принстоне, штат Нью-Джерси, получили в этом году премию Абеля, которую иногда называют Нобелевской премией по математике.
Ави Вигдерсон и Ласло Ловас выиграли за свою работу по разработке теории сложности и теории графов соответственно, а также за соединение этих двух областей.
Когда Ави Вигдерсон и Ласло Ловас начинали свою карьеру в 1970-х годах, теоретическая информатика и чистая математика были почти полностью отдельными дисциплинами. Сегодня они так сблизились, что трудно найти грань между ними. За их большой фундаментальный вклад в обе области и за их объединяющую работу сегодня Ловас и Вигдерсон были удостоены премии Абеля — награды, присуждаемой Норвежской академией наук и литературы и считающейся одной из высших наград в математике.
Своей работой ученые дали толчок области вычислительной сложности — изучению скорости и эффективности алгоритмов.
В чем суть работы лауреатов?
Как говорится в официальном сообщении, этим ученым принадлежит ключевая роль в развитии компьютерных алгоритмов, криптографии и оптимизации вычислений на протяжении последних десятилетий.
В семидесятых годах прошлого столетия произошел всплеск интереса к дискретной математике, которая изучает, например, логические высказывания или графы. Ученым стало понятно, что ее можно применить в компьютерных науках. С помощью теории графов выражают вычислительную сложность — количество ресурсов, необходимых алгоритму для получения результата.
Алгоритмы — это списки инструкций, по сути, рецепт, которому нужно следовать для выполнения задачи. Это может включать решение уравнения, сортировку списка слов в алфавитном порядке или определение самого быстрого маршрута между двумя местами. Некоторые алгоритмы лучше других — они требуют меньшего количества шагов для выполнения задачи, но это не значит, что их проще решить. Отсюда необходимость в целой области исследований, чтобы разобраться в этом, что находится на пересечении математики и информатики.
Вигдерсон работал над всеми крупными открытыми проблемами в области вычислительной сложности. «В науке нет более важных проблем, — подчеркивает он. — Любой процесс это алгоритм. Нейроны в мозгу или планеты Солнечной системы или кризисы на финансовых рынках — все это имеет определенные фиксированные правила. То, что можно применить к компьютерам, можно применить практически ко всему», передает New Scientist.
Вокруг понятия вычислительной сложности строится современная криптография, так как зашифрованной считается информация, алгоритм раскодирования которой без ключа невыполним за разумное время. Графы также используют для создания искусственных нейронных сетей.
По мнению жюри Абелевской премии Норвежской академии наук и литературы, Ласло Ловас и Ави Вигдерсон добились наибольших результатов в дискретной математике. Так, вклад последнего в ускорение и оптимизацию алгоритмов больше, чем любого другого ученого. В своих работах Вигдерсон рассмотрел почти все актуальные проблемы теории сложности, став соавтором более сотни исследователей.
Два исследователя разделят призовой фонд в размере 7,5 млн норвежских крон (более 65 млн рублей).
Эрлангенская программа — выступление 23-летнего немецкого математика Феликса Клейна в Эрлангенском университете, в котором он предложил общий алгебраический подход к различным геометрическим теориям и наметил перспективный путь их развития.
Эллиптическая функция — в комплексном анализе периодическая в двух направлениях функция, заданная на комплексной плоскости. Эллиптические функции можно рассматривать как аналоги тригонометрических. Исторически, эллиптические функции были открыты как функции, обратные эллиптическим интегралам.
Функциональное уравнение — уравнение, выражающее связь между значением функции в одной точке с её значениями в других точках. Многие свойства функций можно определить, исследуя функциональные уравнения, которым эти функции удовлетворяют.
Интегральные преобразования — одни из наиболее мощных средств решения дифференциальных уравнений, как обыкновенных, так, особенно, в частных производных, является метод интегральных преобразований.
Первое доказательство теоремы Абеля — Руффини опубликовано в 1799 году Руффини. В доказательстве было несколько неточностей. В 1824 году полное доказательство было опубликовано Абелем.
Их доказательства основывалось на идеях Лагранжа, связанных с перестановками корней уравнения. Позже эти идеи были развиты в теории Галуа, она позволила сформулировать современное изложение доказательств и послужила отправной точкой в развитии абстрактной алгебры.
Теория групп — раздел общей алгебры, изучающий алгебраические структуры, называемые группами, и их свойства. Группа является центральным понятием в общей алгебре, так как многие важные алгебраические структуры, такие как кольца, поля, векторные пространства, являются группами с расширенным набором операций и аксиом.
Эллиптbческий интегрfл — некоторая f над полем действительных или комплексных чисел.
Эллиптическая функция — в комплексном анализе периодическая в двух направлениях функция, заданная на комплексной плоскости. Эллиптические функции можно рассматривать как аналоги тригонометрических (имеющих только один период). Исторически, эллиптические функции были открыты как функции, обратные эллиптическим интегралам.
Абелевская премия — 2021
Лауреаты Абелевской премии за 2021 год: Ласло Ловас (László Lovász, слева) и Ави Вигдерсон (Avi Wigderson). Фото с сайта abelprize.no
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_
Рис. 3. Примеры кнезеровских графов: \(KG_<5,2>\) (граф Петерсена), \(KG_<5,1>\) (полный граф на пяти вершинах), \(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), то нетрудно видеть, что «случится хотя бы одно из событий» — это, визуально, объединение соответствующих областей. Тогда вероятность, интересующая нас, не больше суммы вероятностей отдельных событий (областей), и вот уже про сумму надо доказать, что она строго меньше единицы.
Рис. 4. Примеры событий, которые могут произойти при одном броске игральной кости
Однако если событий очень много, то такая грубая оценка может превзойти единицу. Но это нелепо, ведь любая вероятность не больше одного! Так вот локальная лемма — это мощное утверждение о том, что если в некотором смысле каждое событие зависит от не слишком большого числа других событий, то не важно, сколько событий всего, важно только количество этих «локальных» зависимостей. Именно оно в итоге отвечает за то, что вероятность объединения кругов окажется строго меньше одного. Здесь, наверное, можно предложить почитать уже упоминавшиеся брошюру Вероятность и алгебра в комбинаторике и книгу Вероятностный метод.
В завершение скажу еще об одном современном направлении в дискретной математике, которое Ловас также поднял на новый уровень. Речь идет о математике так называемых сложных сетей. На практике это Интернет, социальные сети, сети межбанковских взаимодействий, биологические сети и так далее. С точки зрения математики, оказывается, что такие сети в процессе своего роста обладают определенными устойчивыми свойствами. Например, они достаточно разреженные (число ребер имеет тот же порядок роста, что и число вершин). Во всех них наблюдается «закон» шести рукопожатий (между любыми двумя вершинами есть короткие реберные цепочки). Есть и другие, более хитрые, наблюдения. Подробности этой увлекательной науки можно посмотреть в книге Модели интернета. Одним из направлений в этой науке является создание теории «графовых пределов». Подобно тому, как последовательности чисел могут иметь некоторые предельные значения, у последовательности графов также может быть некоторый предел. Именно в нем содержится информация о тех устойчивых свойствах, которые мы наблюдаем в природе. Ласло Ловас — один из мировых лидеров в этой науке.