# Terminology for sparse cuts in graphs

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.

• I'd add edge isoperimetric parameter and (edge) isoperimetric number to this list, both of which are also sometimes used in an ambiguous way. – Holger Feb 4 '11 at 14:27