Publication at Faculty of Mathematics and Physics |
2021
Abstract
For a hereditary class g of graphs, let s(g)(n) be the minimum function such that each n-vertex graph in g has a balanced separator of order at most s(g)(n), and let del(g)(r) be the minimum function bounding the expansion of g, in the sense of bounded expansion theory of Nesetril and Ossona de Mendez. The results of Plotkin et al. (1994) and Esperet and Raymond (2018) imply that if s(g)(n) = Theta(n(1-epsilon)) for some epsilon > 0, then del(g)(r) = Omega(r(1/2 epsilon-1)/polylog r) and del(g)(r) = 0(r(1/epsilon-1) polylog r).
Answering a question of Esperet and Raymond, we show that neither of the exponents can be substantially improved. (C) 2020 Elsevier Ltd. All rights reserved.