Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Germany

European Research Council grant · Running

WYDRA Towards a unified structure theory for dense graphs

Coordinator
Technische Universitat Darmstadt, Germany
Runs
1 October 2026 to 30 September 2031
Status
Running
EU funding
€2.0m
Total cost
€2.0m
Partners
2 organisations in 2 countries
Type
European Research Council grant
Grant agreement
101230549

What the project is doing

In the project's own words, from its summary on CORDIS.

The fields of graph algorithms and of structural graph theory enjoy a particularly fruitful symbiosis, marked by a rich exchange of techniques, concepts, and inspirations. At this point, structural graph theory provides a comprehensive toolbox for the treatment of sparse graphs. Compared to this, our understanding of dense graphs is much more fragmented and incomplete. Motivated by a recent wave of advances in this topic, we propose to launch a systematic investigation of links between the existing islands of knowledge, with the goal of constructing a solid and unified theory of structure for dense graphs.

To this end, we aim to consolidate the following three major areas, and explore the connections between them: - the logic theory, which adopts the point of view of model theory, and sees graphs as relational structures on which various logics can be employed; - the algebraic theory, or the theory of vertex-minors, which studies graphs through the linear-algebraic properties of their adjacency matrices over the binary field F_2; and - the coarse theory, which views graphs as metric spaces and provides tools and techniques for describing their large-scale structure.

The outcome of the project will be a comprehensive theory offering concepts, techniques, and tools for the structural treatment of dense graphs. We expect a wealth of combinatorial and algorithmic applications, as well as opening of new research perspectives at the intersection of graph theory and algorithmics.

Topics

Who is involved

OrganisationCityCountryRole
Technische Universitat DarmstadtDarmstadtGermanyCoordinator
Uniwersytet WarszawskiWarszawaPolandParticipant

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI