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

<p>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</p>

<p>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</p>

CC BY-SA 3.0
2013-06-06T04:26:08.753Z
2013-06-06T04:26:08.753Z
NAg
<p>let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is </p>

<p>$$\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 .. </p>

<graph-theory><graph-algorithms><expanders><partition-problem>
Expansion vs Sparsest cut
John Peca
# Expansion vs Sparsest cut

(Asked by: username_0 on 2013-05-31)

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

**Tags:** graph-theory, graph-algorithms, expanders, partition-problem


---

## 1 answers

### Answer by username_1 on 2013-06-06. Score: 0 | Accepted answer

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


---

