На днях норвежская академия наук объявила лауреатов Абелевской премии 2021 года.

МЕНЮ


Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Дорогие коллеги!

На днях норвежская академия наук объявила лауреатов Абелевской премии 2021 года. Ими стали известные математики Ласло Ловас (La?szlo? Lova?sz) и Ави Вигдерсон (Avi Wigderson) за вклад в развитие информатики и дискретной математики. В честь этого замечательного события опубликуем небольшой текст из статьи Д. Ильинского, А. Райгородского и А. Скопенкова посвящённый знаменитой локальной лемме Ловаса. Помещаем в текущем посте эту статью, и еще одну замечательную статью А. Ремизовой, А. Скопенкова посвящённую простому доказательству данной леммы.

Локальная лемма Ловаса была доказана в 1973 году выдающимся венгерским математиком Ласло Ловасом. Впрочем, тогда Ловасу было всего 25 лет, и, хотя яркие результаты у него уже к тому времени были, все-таки на тот момент его воспринимали не как классика, но как восходящую звезду. Он уже был трехкратным победителем международных математических олимпиад (1964, 1965 и 1966 годов). Классиком Ловас станет позже, и весьма серьезную роль в этом сыграет доказанная им Локальная лемма. Разумеется, не только она: будет и топологический метод в комбинаторике, и мощные результаты в теории алгоритмов, и значительный вклад в науку ографовых пределах, и многое другое. Тем не менее, Локальная лемма — это замечательный инструмент вероятностной комбинаторики, благодаря которому были получены и продолжают получаться многочисленные яркие результаты в области дискретной математики и теории алгоритмов.

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

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

Комментарии: