<p>I think (2) is called the uniform sparsest cut. The term non-uniform is used for the version where each pair ij of vertices has a separate demand d(ij) and the cut sparsity is E(S,V-S)/d(S,V-S) where d(S,V-S) is the demand between S and V-S. </p>

CC BY-SA 2.5
2011-01-30T22:25:40.233Z
You are right, and I meant to write "uniform", I'll edit the post
Luca Trevisan
CC BY-SA 2.5
2011-01-30T21:20:57.483Z
2011-01-30T21:20:57.483Z
Chandra Chekuri
<p>I have found some ambiguity in how the graph parameters <i>edge-expansion</i>, <i>uniform sparsest cut</i> and <i>conductance</i> are defined and denoted.</p>

<p>My questions are: what are the definitions that best match the primary sources and the current use? Does what follows sound right?</p>

<p>(1) The <i>Cheeger constant</i> of a graph, denoted $h$ is</p>

<p>$h(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ |S|, |V-S| \}}$</p>

<p>where $\textrm{Edges}(S,V-S)$ denotes the number of (or the total weight of) edges with one endpoint in $S$ and one endpoint not in $S$.</p>

<p>(2) The <i>uniform sparsest cut</i> of a graph, denoted $\phi$ is</p>

<p>$\phi(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{|S| \cdot |V-S|}$</p>

<p>Notes:</p>

<ul>
<li> $h$ is also called the <i>edge expansion</i> of $G$
<li> $h$ and $|V|\cdot \phi$ are within a factor of 2, so approximating one problem is equivalent to approximating the other, up to a constant loss in the approximation ratio
</ul>

<p>(3) The <i>conductance</i> of a graph, unfortunately also usually denoted $\phi$. Maybe we should use $\sigma$ for the sparsest cut parameter?</p>

<p>$\textrm{conductance}(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ \textrm{vol}(S), \textrm{vol}(V-S) \}}$</p>

<p>where $\textrm{vol}(S)$ is the sum of the degrees of the vertices of $S$</p>

<p>Note:</p>

<ul>
<li> If $G$ is $d$-regular, then $\textrm{conductance}(G) = h(G)/d$. In the irregular case, the conductance is incomparable with $h$ and $\phi$
</ul>

<p>(4) Finally, as an intermediate problem to use to give relaxations of the conductance problem, I have seen the following problem, that does not seem to have a name ("volume-weighted sparsest cut"? what letter should be used to denote it?)</p>

<p>$\min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\textrm{vol}(S) \cdot \textrm{vol}(V-S)}$</p>

<p>which is $\phi/d^2$ in regular graphs, and that scaled by $\textrm{vol}(V)$ is within a factor of 2 from the conductance.</p>

CC BY-SA 2.5
2011-02-04T14:27:27.350Z
I'd add [edge isoperimetric parameter](http://en.wikipedia.org/wiki/Isoperimetric_inequality#Isoperimetric_inequalities_for_Graphs) and (edge) isoperimetric number to this list, both of which are also sometimes used in an ambiguous way.
Holger
<graph-theory><co.combinatorics><terminology><expanders><spectral-graph-theory>
Terminology for sparse cuts in graphs
Luca Trevisan
# Terminology for sparse cuts in graphs

(Asked by: username_0 on 2011-01-30)

I have found some ambiguity in how the graph parameters *edge-expansion*, *uniform sparsest cut* and *conductance* are defined and denoted.

My questions are: what are the definitions that best match the primary sources and the current use? Does what follows sound right?

(1) The *Cheeger constant* of a graph, denoted $h$ is

$h(G) := \min\_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ |S|, |V-S| \}}$

where $\textrm{Edges}(S,V-S)$ denotes the number of (or the total weight of) edges with one endpoint in $S$ and one endpoint not in $S$.

(2) The *uniform sparsest cut* of a graph, denoted $\phi$ is

$\phi(G) := \min\_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{|S| \cdot |V-S|}$

Notes:

* $h$ is also called the *edge expansion* of $G$* $h$ and $|V|\cdot \phi$ are within a factor of 2, so approximating one problem is equivalent to approximating the other, up to a constant loss in the approximation ratio

(3) The *conductance* of a graph, unfortunately also usually denoted $\phi$. Maybe we should use $\sigma$ for the sparsest cut parameter?

$\textrm{conductance}(G) := \min\_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ \textrm{vol}(S), \textrm{vol}(V-S) \}}$

where $\textrm{vol}(S)$ is the sum of the degrees of the vertices of $S$

Note:

* If $G$ is $d$-regular, then $\textrm{conductance}(G) = h(G)/d$. In the irregular case, the conductance is incomparable with $h$ and $\phi$

(4) Finally, as an intermediate problem to use to give relaxations of the conductance problem, I have seen the following problem, that does not seem to have a name ("volume-weighted sparsest cut"? what letter should be used to denote it?)

$\min\_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\textrm{vol}(S) \cdot \textrm{vol}(V-S)}$

which is $\phi/d^2$ in regular graphs, and that scaled by $\textrm{vol}(V)$ is within a factor of 2 from the conductance.

**Tags:** graph-theory, co.combinatorics, terminology, expanders, spectral-graph-theory
> **Comments:**
> **username_1**: I'd add [edge isoperimetric parameter](http://en.wikipedia.org/wiki/Isoperimetric_inequality#Isoperimetric_inequalities_for_Graphs) and (edge) isoperimetric number to this list, both of which are also sometimes used in an ambiguous way.  

---

## 1 answers

### Answer by username_2 on 2011-01-30. Score: 6

I think (2) is called the uniform sparsest cut. The term non-uniform is used for the version where each pair ij of vertices has a separate demand d(ij) and the cut sparsity is E(S,V-S)/d(S,V-S) where d(S,V-S) is the demand between S and V-S.

> **Comments:**
> **username_0**: You are right, and I meant to write "uniform", I'll edit the post  

---

