Invitation to Sparsity
Org: Zdeněk Dvořák
- PATRICE OSSONA DE MENDEZ, CNRS, École des Hautes Études en Sciences Sociales
A model theoretical approach to sparsity [PDF]
The notion of sparse graphs, although vague, usually witnesses a qualitative leap in structural properties. It appears that this structural differentiation agrees with the main dividing lines of model theory: stability and dependence. We survey some mutual enrichments of structural graph theory and model theory and show how model theory provides interesting tools to handle sparse graphs and suggests intriguing problems, whose significance encompasses both graph theory, theoretical computer science, and model theory.
- ZDENĚK DVOŘÁK, Charles University
Sparsity: Concepts and applications [PDF]
I will give a basic overview of the hierarchy of sparsity notions and the relationships between them, demonstrate their importance in several interesting applications, and set up the stage for the other talks in this minisymposium.
- MICHAŁ PILIPCZUK, University of Warsaw
Algorithmic aspects II [PDF]
During the talk we will show how to make use of forbidden structures in sparse graphs, such as half-graphs in their powers, to design efficient parameterized algorithms for various problems. This topic will also serve as an excuse to survey some on-going work on constructing a theory for classes of well-structured dense graphs.
- FELIX REIDL, Birkbeck University of London
Algorithmic aspects I [PDF]
One of the beautiful aspects of the theory of sparse classes are the various notions of sparseness that turn out to be intrinsically connected. From the algorithmic side, this provides us with a nice toolkit to design exact, parameterized and approximation algorithms. In this talk we will feature a few interesting problems and see how the toolkit can be applied.
- SEBASTIAN SIEBERTZ, University of Bremen
Characterizing sparsity by games. [PDF]
The two key notions of uniform sparseness, bounded expansion and nowhere denseness, admit many equivalent characterizations. In this talk, I will present very intuitive game characterizations of both concepts.