Back to Search
Start Over
A note on sublinear separators and expansion
- 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 :
- Mathematics - Combinatorics
05C75
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2001.09679
- Document Type :
- Working Paper