Exact value of separator exponent b_ε

Informal open question on the exact value of $b_\varepsilon$ · arXiv:2001.09679

arXiv Informal medium confidence— first stated 2020-07-07

Status open medium confidence

Dvořák establishes the bounds $\frac{1}{2\varepsilon}-1\leq b_\varepsilon\leq\frac{1}{2\varepsilon}-\frac{1}{2}$ for $0<\varepsilon<\frac{1}{2}$ and asks whether the remaining gap of $\frac{1}{2}$ can be closed; no follow-up paper resolving this question was found in five web searches. The question of whether $b_\varepsilon$ is discontinuous at $\varepsilon=1/2$ remains open.

Reviewer notes. No follow-up work resolving the gap between the upper and lower bounds on $b_\varepsilon$ was found in the indexed literature. The paper is 6 years old (2020–2026), so medium rather than high confidence is assigned. Related work on strongly sublinear separators (e.g., arXiv:2208.10074 on product structure, and a SoCG 2025 paper on sphere intersection graphs) continues the broader programme but does not appear to address this specific bound-tightening question.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It is unclear whether the upper or the lower bound on $b_\varepsilon$ can be improved for $0<\varepsilon<\frac{1}{2}$. While the fact that $b_{1/2}=0$ matches the lower bound suggests that a better construction improving the upper bound in general could exist, it is also plausible that this is just a "dimension 2" artifact and in fact the lower bound might be possible to improve for $\varepsilon<1/2$ (possibly leading to discontinuity of $b_\varepsilon$ at $\varepsilon=1/2$).

Context

After establishing $\frac{1}{2\varepsilon}-1\leq b_\varepsilon\leq\frac{1}{2\varepsilon}-\frac{1}{2}$ for $0<\varepsilon<\frac{1}{2}$ and $b_\varepsilon=0$ for $\frac{1}{2}\leq\varepsilon\leq 1$, the paper notes that the remaining gap of $\frac{1}{2}$ in the bounds on $b_\varepsilon$ is unresolved, and that the behaviour at $\varepsilon=1/2$ makes the problem structurally interesting.

Notes. Stated as an open remark in the concluding summary. 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