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 ..


1 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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.