Back to Search Start Over

A note on sublinear separators and expansion

Authors :
Dvořák, Zdeněk
Publication Year :
2020

Abstract

For a hereditary class C of graphs, let s_C(n) be the minimum function such that each n-vertex graph in C has a balanced separator of order at most s_C(n), and let nabla_C(r) be the minimum function bounding the expansion of C, in the sense of bounded expansion theory of Ne\v{s}et\v{r}il and Ossona de Mendez. The results of Plotkin, Rao, and Smith (1994) and Esperet and Raymond (2018) imply that if s_C(n)=Theta(n^{1-epsilon}) for some epsilon>0, then nabla_C(r)=Omega(r^{1/(2.epsilon)-1}/polylog r) and nabla_C(r)=O(r^{1/epsilon-1}polylog r). Answering a question of Esperet and Raymond, we show that neither of the exponents can be substantially improved.<br />Comment: 10 pages, no figures; updated according to the reviewer remarks

Subjects

Subjects :
Mathematics - Combinatorics
05C75

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2001.09679
Document Type :
Working Paper