Towards a unified structure theory for dense graphs

Objective

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.