Existence and Counting

Jarik Nesetril
Charles University, Prague

We introduce the dichotomy between classes of graphs (and more generally of
structures): Nowhere Dense and Somewhere Dense classes.
We show how this dichotomy naturally arises and show its several characterizations. Particularly, we show how these classes can be defined by the limit frequencies of its subgraphs (which are integral and can be interpreted as degrees of freedom).

This is a joint work with Patrice Ossona de Mendez (EHESS Paris).

Back to Workshop III: Topics in Graphs and Hypergraphs