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.
