as $$h(G) = \min_{\substack{\emptyset \ne S \subset V \\ |S| \le |V|/2}}\frac{|E(S,\bar S)|}{k|S|},$$ where $E(S,\bar S)$ is the set of edges with one endpoint in $S$ and one endpoint in $\bar S$.

If $h(G) \ge \epsilon$ for some constant $\epsilon > 0$, then $G$ is said to be an [*$\epsilon$-combinatorial expander*]{}. A family of graphs $\{G_i\}_{i \in {\mathbb{N}}}$ is called a family of $\epsilon$-combinatorial expanders if there exists a constant $\epsilon > 0$ such that $h(G_i) \ge \epsilon$ for every $i \in {\mathbb{N}}$. Intuitively it means that the graph is very well connected, and hence the random walk on it is not likely to “get stuck” in a small subset of vertices.

A [*random walk*]{} on $G$ can be described by the following process. We start at a random vertex $v_0 \in V$. Then, if after $t$ steps we are at vertex $v_t$, we choose one of the edges containing $v_t$ uniformly at random and move to its other endpoint. Thus, for any $u,v \in V$ $$\Pr[v_{t+1} = v \;|\; v_t = u] = \frac{A(u,v)}{k}.$$

Denote by $\pi_0 \in {\mathbb{R}}^V$ the probability distribution from which $v_0$ is chosen. Then the random walk on $G$ yields a sequence of probability distributions 