Jaroslav Nešetřil received the Nerode Prize for his pioneering work in graph theory

Jaroslav Nešetřil, together with French mathematician Patrice Ossona de Mendez, has been awarded the 2025 Nerode Prize by the European Association for Theoretical Computer Science (EATCS). They laid the foundations for a significant area of structural graph theory, known as Sparsity. Their work has not only profoundly influenced pure mathematics but also has practical applications in algorithmic graph theory, computational complexity, and mathematical logic.

Professor Jaroslav Nešetřil is a member of the Learned Society of the Czech Republic and works at the Computer Science Institute of Charles University (IUUK), as does Professor Patrice Ossona de Mendez, who also holds an affiliation with the École des hautes études en sciences sociales (EHESS) in Paris. The award was presented to them in Warsaw.

The Nerode Prize is given for exceptional work in the field of multivariate algorithms and is named after the distinguished American mathematician and logician Anil Nerode. It recognizes influential and lasting contributions that have pushed the boundaries of the field. The award is given for a single paper or a series of papers published within the last fifteen years, and its laureates are selected by a committee of leading experts.

This year’s prize was awarded for a fundamental contribution that laid the foundations of Sparsity: an area of structural graph theory that focuses on the concepts of nowhere dense graph classes and graph classes with bounded expansion. These two definitions robustly capture the concept of local, structural sparseness in graphs and finite structures. In their acclaimed series of papers and their monography Sparsity, published by Springer in 2012, Nešetřil and Ossona de Mendez introduced key notions and demonstrated their fundamental character. They succeeded in proving a wide range of properties and equivalent characterizations, thereby creating a powerful toolbox of techniques for working with sparse graphs and structures.

As their previous work has shown, this toolbox can be used to design parameterized algorithms for problems of a local nature. Over the years, this has led to several breakthrough results in parameterized complexity, particularly to major advances in understanding the complexity of problems definable in First-Order logic. The pioneering work of Nešetřil and Ossona de Mendez created an impressive bridge between structural graph theory, logic, model theory and multivariate algorithmics, leaving a lasting mark on all these fields. The work of both scientists was supported by an ERC Synergy Grant from the European Research Council.

Photo: IUUK

adapted from an article on the Faculty of Mathematics and Physics of Charles University website