One-sided sublinear separator expansion equality
Informal conjecture $b'_\varepsilon = b_\varepsilon$ for $0<\varepsilon<\tfrac{1}{2}$ · arXiv:2001.09679
Status open low confidence
No follow-up work resolving the conjecture $b'_\varepsilon = b_\varepsilon$ for $0 < \varepsilon < \frac{1}{2}$ was found in five web calls. Dvořák published related work on weighted sublinear separators (Journal of Graph Theory, 2022) and, with Wood, on product structure of graph classes with strongly sublinear separators (arXiv:2208.10074, 2022), but neither paper appears to address this specific parameter-equality question. The conjecture is now six years old; absence of a resolution in the indexed literature is somewhat surprising for a problem of this age, but the question is technically narrow and may simply not yet have attracted a focused attack.
Reviewer notes. The Wiley page for Dvořák's 2022 JGT paper 'On weighted sublinear separators' (DOI 10.1002/jgt.22777) returned HTTP 402 (paywall) so its relevance to the conjecture could not be verified; it is not included in since_posted. The arXiv:2208.10074 paper by Dvořák–Wood works in an adjacent area but its abstract does not mention the b_epsilon/b'_epsilon parameters or the conjecture. No arXiv preprint for the 2022 JGT paper was found.
Context
The parameter $b'_\varepsilon$ is defined analogously to $b_\varepsilon$ but with the one-sided condition $s_\mathcal{G}(n)=\Omega(n^{1-\varepsilon})$ rather than $\Theta(n^{1-\varepsilon})$; equality $b'_\varepsilon=b_\varepsilon=0$ already holds for $\frac{1}{2}\leq\varepsilon\leq 1$, but extending this to $0<\varepsilon<\frac{1}{2}$ requires showing that a one-sided lower bound on separators alone forces the same expansion lower bound, which is not obvious.
Notes. Conjectural language 'It seems likely' appears in the final section. PDF source.
Source paper
A note on sublinear separators and expansion
Zdeněk Dvořák · 2020-07-07
https://arxiv.org/abs/2001.09679
PDF source