The Norwegian Academy of Science and Letters has awarded the 2021 Abel Prize to László Lovász and Avi Wigderson “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”. https://www.abelprize.no/
László Lovász is an emeritus professor of Eötvös University (Budapest, Hungary). Currently he is leading the research group DYNASNET at the Rényi Institute, supported by a Synergy grant of the European Research Council.
Mathematicians are usually characterized either as problem-solvers or theory-builders. Lovász is both.
He has solved several hard problems in combinatorics that had been open for a long time:
the perfect graph conjecture in 1972, https://en.wikipedia.org/wiki/Perfect_graph_theorem
the chromatic number of Kneser graphs in 1978, https://en.wikipedia.org/wiki/Kneser_graph
the Shannon capacity of graphs in 1979, https://en.wikipedia.org/wiki/Shannon_capacity_of_a_graph
– just to name a few. His ingenious solutions were often based on ideas inspired by seemingly unrelated mathematical areas. For example, in the case of the Kneser graphs he used topological methods, thereby laying the foundations of topological combinatorics, a novel area of research. https://en.wikipedia.org/wiki/Topological_combinatorics
Similarly, the ideas he used for determining the Shannon capacity of graphs led to the theory of semidefinite programming. Furthermore, the Lovász local lemma, which relaxes the independence condition in the application of probabilistic methods in combinatorics, has been used extensively since its invention in 1973. https://en.wikipedia.org/wiki/Lovász_local_lemma
Lovász was an early champion of the mathematical theory of algorithms. He published a book on this subject with Péter Gács in 1978 in Hungarian. Together with the Lenstra brothers Arjen and Hendrik, he invented the LLL lattice base reduction algorithm, which has been used for a great variety of purposes: for factoring polynomials, for disproving the Mertens conjecture, and more recently in cryptography. https://en.wikipedia.org/wiki/Lenstra-Lenstra-Lovász_lattice_basis_reduction_algorithm
To demonstrate his theory-building accomplishments, it is enough present the long list of books written by him: Combinatorial problems and exercises (1979), Matching theory (with M. Plummer, 1986), An algorithmic theory of numbers, graphs, and convexity (1986), Geometricalgorithms and combinatorial optimization (with M. Grötschel and A. Schrijver, 1988), Greedoids (with B. Korte and R. Schrader, 1991), Discrete mathematics: elementary and beyond (with J. Pelikán and K. Vesztergombi, 2003), Large networks and graph limits (2012), Graphs and geometry (2019).
The theory of graph limits, which he developed in collaboration with C. Borgs, J. Chayes, B. Szegedy, V.T. Sós, and K. Vesztergombi, also serves as the mathematical foundation for his current research on the dynamics of networks. The investigations of his research group have relevance for mathematical modelling of disease propagation that can be used in controlling the recent pandemic.
As the citation from the Norwegian Academy emphasized, Lovász had a leading role in elevating the field of discrete mathematics from an isolated, sometimes even disregarded area to one of the central branches of modern mathematics. When he started research in graph theory, this area was considered by many leading mathematicians as a collection of problems, some of which perhaps interesting and difficult, but which lack significance for the really important parts of mathematics. Now, as the laudation of this year’s Abel Prize winners aptly formulated, discrete mathematics has taken its deserved place as one of the fundamental branches of mathematics.
For most of his career László Lovász was a professor at Eötvös University in Budapest, but he has spent considerable time at other institutions: at the University of Szeged, at Yale University and at Microsoft Research.
Lovász is not only an outstanding mathematician, but he did a great job at serving the scientific community as the president of the International Mathematical Union (2007-2010) and the president of the Hungarian Academy of Sciences (2014-2020).
Congratulations, Laci! We wish you further successes in your research.
More news:
ABEL PRIZE AWARDED TO ERC GRANTEE LÁSZLÓ LOVÁSZ - erc.europa.eu