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
| Organisation | City | Country | Role |
|---|---|---|---|
| Technische Universitat Darmstadt | Darmstadt | Germany | Coordinator |
| Uniwersytet Warszawski | Warszawa | Poland | Participant |
Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI