What do a road map, the internet and a family tree have in common? All of them, in the most simplified sense, are collections of interconnected elements named graph. How can mathematics describe their structure? This is the aim of research of Prof. Michał Pilipczuk from the Faculty of Mathematics, Informatics and Mechanics at the University of Warsaw, who has received a Consolidator Grant from the European Research Council to carry out the project WYDRA. It is the second ERC grant in his career.

The first one was BOBR. In 2020, Prof. Michał Pilipczuk – seven years after completing his PhD – obtained his first European Research Council (ERC) Starting Grant. In that project, he studied the structural and decomposition properties of networks and used them to create fast computational methods for solving difficult problems.

Networks also feature in WYDRA, the project for which the researcher received a Consolidator Grant on 9th December.

„WYDRA concerns graphs. These are fundamental mathematical objects used to model all kinds of networks. Graphs appearing in applications often have a specific structure,” says Prof. Pilipczuk. He points the examples: road networks are „flat”, while social networks consist of dense clusters and sparser connections between them.

Mathematics and computer science

It has long been known that research into graph algorithms and the mathematical theory of their structure permeate and complement one another. For so-called sparse graphs – those in which the number of connections between elements is relatively small – they can be analysed using a well-developed set of tools and methods. The situation is completely different for dense graphs (with many edges): knowledge about them remains incomplete. Prof. Michał Pilipczuk has decided to tackle this challenge.

„We aim to develop a coherent and robust theory describing the structure of dense graphs,” says the scientist, adding that his intention is to combine three main approaches:

• the logical approach, in which the graph is treated as a set of interconnected objects and described using tools from mathematical logic and model theory;
• the algebraic approach, known as the theory of vertex-minors. Here, studying a graph is based on analysing the properties of its adjacency matrix (large tables describing connections) using methods of linear algebra over the binary field (the simplest possible mathematical field);
• the coarse approach, which considers the graph as a kind of metric space. This perspective makes it possible to study the large-scale structure of the graph without delving into fine details visible only locally.

„When describing structure in graphs, we usually think in terms of various decompositions. For instance, we may see two clusters in a large network, separate them, and notice that there are few connections between them – which allows us to „solve” them separately. To do this, we need the language of mathematics: structural graph theory, which proves theorems about network decompositions,” explains Prof. Pilipczuk, adding: „We expect that the results of our research will pave the way for many new applications – in both combinatorics and algorithm design. We also hope it will indicate interesting directions for further research at the intersection of graph theory and theoretical computer science.”