Ласло Ловас¶

Ласло Ловас (венг. Lovász László, род. 9 марта 1948, Будапешт) — венгерский математик, специализирующийся в области комбинаторики, теории графов, теории сложности вычислений и комбинаторной оптимизации. Лауреат премии Вольфа по математике (1999) и премии Абеля (2021). Внёс фундаментальный вклад в развитие алгоритмической теории графов, вероятностного метода в комбинаторике и теории приближённых алгоритмов.

¶Биография

Ласло Ловас родился в Будапеште в семье математиков. Его отец, Ласло Ловас-старший, был профессором математики в Будапештском университете. С раннего возраста проявил выдающиеся способности к математике: в 14 лет выиграл первую олимпиаду по математике, а в 1965 году, в возрасте 17 лет, завоевал золотую медаль на Международной математической олимпиаде (IMO) в Берлине.

В 1966 году поступил в Будапештский университет имени Лоранда Этвёша, где изучал математику и физику. В 1970 году получил диплом, а в 1971 году — докторскую степень (PhD) под руководством Пала Эрдёша. В 1972 году защитил кандидатскую диссертацию (аналог докторской) в Венгерской академии наук.

С 1973 по 1978 год работал в Будапештском университете, затем перешёл в Университет имени Йожефа Аттилы (Сегед). В 1980-х годах занимал должности в Йельском университете (США) и Принстонском университете. В 1993 году вернулся в Венгрию и стал профессором Будапештского университета, а с 2006 года — президентом Венгерской академии наук (до 2011 года). В 2014 году вышел на пенсию, но продолжает активную научную деятельность.

¶Научные достижения

¶Комбинаторика и теория графов

Ловас является одним из создателей современной алгоритмической теории графов. Его работы охватывают широкий спектр тем: от фундаментальных свойств графов до разработки эффективных алгоритмов.

• Лемма Ловаса (Local Lemma): Вероятностный метод, позволяющий доказывать существование объектов с заданными свойствами даже при наличии большого числа слабых зависимостей. Лемма широко применяется в комбинаторике, теории графов и информатике.
• Теорема Ловаса — Хайнала: Устанавливает связь между хроматическим числом графа и его свойствами, связанными с раскраской рёбер.
• Теорема о разбиении графа: Доказывает, что любой граф с достаточно большим числом вершин содержит либо большой полный подграф, либо большой независимый набор.
• Алгоритм Ловаса — Шрайера: Эффективный алгоритм для нахождения максимального независимого множества в графах с ограниченной степенью.

¶Теория сложности и оптимизация

Ловас внёс значительный вклад в теорию сложности вычислений, особенно в области приближённых алгоритмов и комбинаторной оптимизации.

• Алгоритм Ловаса — Шрайера для задачи о клике: Один из первых алгоритмов, дающих гарантированное приближение для NP-трудной задачи.
• Теорема Ловаса — Шрайера о приближении: Устанавливает границы точности приближения для некоторых NP-трудных задач.
• Метод эллипсоидов: Ловас совместно с Ласло Шрайером и Александром Шрайером разработал метод эллипсоидов для решения задач линейного программирования, который стал основой для многих алгоритмов комбинаторной оптимизации.

¶Вероятностный метод

Ловас активно развивал вероятностный метод в комбинаторике, который использует случайные процессы для доказательства существования объектов с заданными свойствами. Его работы в этой области включают:

• Лемма Ловаса (Local Lemma): Позволяет доказывать существование объектов даже при наличии большого числа слабых зависимостей.
• Теорема Ловаса — Шрайера о случайных графах: Устанавливает свойства случайных графов, такие как распределение степеней вершин и наличие циклов.

¶Другие области

Ловас также внёс вклад в теорию чисел, алгебраическую топологию и теорию игр. Его работы по теории чисел включают доказательство гипотезы Эрдёша — Гинзбурга — Цива (совместно с Палом Эрдёшем и Абрахамом Гинзбургом). В теории игр он разработал алгоритмы для решения игр с неполной информацией.

¶Основные публикации

Ловас является автором более 300 научных статей и нескольких монографий. Наиболее известные книги:

• «Combinatorial Problems and Exercises» (1979) — сборник задач по комбинаторике, переведённый на многие языки.
• «An Algorithmic Theory of Numbers, Graphs and Convexity» (1986) — монография по алгоритмической теории чисел и графов.
• «Geometric Algorithms and Combinatorial Optimization» (1988, совместно с Ласло Шрайером) — фундаментальный труд по комбинаторной оптимизации.
• «Large Networks and Graph Limits» (2012) — книга о теории графовых пределов.

¶Награды и признание

• Премия Вольфа по математике (1999) — за фундаментальный вклад в комбинаторику, теорию графов и теорию сложности.
• Премия Абеля (2021) — за выдающиеся достижения в области математики, особенно за развитие вероятностного метода и алгоритмической теории графов.
• Премия имени Неймана (1999) — за вклад в компьютерные науки.
• Медаль имени Бояи (2000) — высшая награда Венгерской академии наук.
• Членство в Венгерской академии наук (с 1985), Национальной академии наук США (с 2006), Лондонского королевского общества (с 2012) и других академий.

¶Интересные факты

• Ловас является одним из самых цитируемых математиков в мире: его работы имеют более 50 000 цитирований.
• В 2014 году он был избран президентом Международного математического союза (IMU) на срок 2015–2018 годов.
• Ловас известен своей педагогической деятельностью: он подготовил более 30 докторов наук, многие из которых стали ведущими математиками.
• Его имя носит несколько математических объектов: лемма Ловаса, теорема Ловаса — Хайнала, алгоритм Ловаса — Шрайера.

¶Критика

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

¶Источники

• Lovász, L. (1979). Combinatorial Problems and Exercises. North-Holland.
• Lovász, L., & Schrijver, A. (1988). Geometric Algorithms and Combinatorial Optimization. Springer.
• Lovász, L. (2012). Large Networks and Graph Limits. American Mathematical Society.
• «László Lovász — Biography». The Abel Prize. 2021.
• «László Lovász — Wolf Prize». Wolf Foundation. 1999.
• «László Lovász — Institute for Advanced Study». IAS. 2020.