The notion of bounded expansion has been introduced by Nešetřil and Ossona de Mendez as a general concept of sparsity. Classes of graphs of bounded expansion are interesting as they generalize many known sparse classes (as planar graphs, graphs of bounded degree, graphs excluding a minor, etc.). Moreover, several algorithmic problems that are known to be computationally hard in general turn out to be solvable in polynomial time when the inputs are taken in a class of bounded expansion fixed in advance.

On the other hand, classes of graphs with (balanced) sublinear separators are extensively used in the design of algorithms (with “Divide and Conquer” type techniques for instance) and enjoy nice structural properties. An example of graphs with sublinear separators is the class of planar graphs, by a classic result of Lipton and Tarjan.

The topic of this talk is the links between these two notions. Let C be a subgraph-closed class of graphs. Dvořák and Norin proved that graphs in C have sublinear balanced separators iff they have polynomial expansion. They conjectured that if the balanced separators in C have size O(n^{1−δ}) (for some 0 < δ ≤ 1), then the expansion in C is O(k^{c/δ}), for some constant c. We prove this conjecture. This is joint work with Louis Esperet.