Expansion vs Sparsest cut

Question

let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is

$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$ where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges between S and $\bar{S}$. Expansion of graph G is $$\alpha(G)=\min_{\emptyset\neq S\subsetneq {V}}\alpha(S)$$ Sparsity $\mathcal S_G$ of graph G is $$\mathcal S_G=\min_{\emptyset\neq S\subsetneq {V}}\frac{|E(S,\overline S)|}{|S||\overline S|} $$ It is easy to see, that $$\frac{n}{2} \mathcal{S}_G\leq \alpha(G) \leq (n-1)\mathcal{S}_G$$ where $n=|V|$. Solution for Expansion Problem is to find set $S\subsetneq V$ such that $\alpha(S)=\alpha(G)$ Solution for Uniform Sparsest Cut Problem is to find set $S\subsetneq V$ such that $$\frac{|E(S,\overline S)|}{|S||\overline S|}=\mathcal S_G$$. My question is, is there a graph for which there are different solution for Expansion Problem and for Uniform Sparsest Cut Problem? Thank you for any ideas ..

Answer 1

I think there may be multiple instances of such graphs. One pathological case that can be constructed is as follows

Consider three disjoint vertex sets S,T,O. S is a single vertex of degree d+1 with all of edges going into the set O, i.e. there are no edges between S and T. Let O be a very large set and let the edges inside O be such that O is a clique. Now the idea is that we will set edges such that T has smaller expansion than S but T will have greater sparsity. So essentially such that S is the smallest sparsity set and T is the smallest expansion. Set up edges such that T is a clique and every vertex in T has d edges going into O. Suppose that |O| and |T| >> d

Now clearly T is the set with smallest expansion (of expansion d) (this is not hard to see because subsets of T and O have a lot of edges going out). Once again the smallest sparsity sets would be either T or S. Sparsity of S = d+1 / |O| + |T| and Sparsity of T = d / |O| + 1 . Given our chosen set of parameters. Sparsity of T > Sparsity of S