Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets:

$$ h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ , $$ with

$$\phi(S) = \frac{ E(S,\bar{S}) }{ \vert S \vert } \ .$$

This naturally defines some notion of "small set" expander. On the other hand a graph is usually said to be expander if $h(G',\frac{1}{2}) \geq \epsilon$ for some sufficiently large $\epsilon$.

My question is: can small set expansion be concentrated into regular expansion? Formally, say that, for some $\delta$, the graph $G$ obeys $h(G, \delta) \geq \epsilon$, does there exist universal constants $c_1,c_2 > 0$ such that there exists a subgraph $G'\subset G$ on $m \geq c_1 \delta n$ vertices, and $h(G',\frac{1}{2}) \geq c_2 \epsilon$ ? I could also settle for degree-depend bounds.

In short: when a graph has some degree of small set expansion, can we show the existence of a small sized proper expander? The only resource I could find on this question is this paper https://arxiv.org/pdf/2001.01522.pdf, but the guarantee on the parameters are much weaker.

Edit: I think I found a way to show that $h(G',\frac{1}{2}) \geq c_2 \epsilon/\log(n)$ is possible.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.