Edge isoperimetric constant convention

PDF p. 20: Remark 3.5, following Lemma 3.4

Let $G=(V,E)$ be a finite undirected graph with at most one edge between any pair of vertices, possible self-loops, and $n=\mathrm{\mid }V\mathrm{\mid }\ge 2$. For $X\subseteq V$, write $X^c=V\setminus X$ and let $e(X,X^c)$ count edges between $X$ and $X^c$, each once. The edge isoperimetric constant, or Cheeger constant, in the unnormalized cut convention is

$h(G):={\min }_{\begin{array}{c}X\subseteq V\\ 0<\mathrm{\mid }X\mathrm{\mid }\le n\mathrm{/}2\end{array}}\frac{e(X,X^c)}{\mathrm{\mid }X\mathrm{\mid }}\mathrm{.}$

Thus the minimum ranges over all nonempty vertex subsets of size at most half of $n$. For $n=1$ this convention leaves $h(G)$ undefined, since there is no admissible subset.

Adjacency, degrees, graph Laplacian, and spectral notation

Oriented edge count between sets

The cardinality | A| of a finite set

Maximum and minimum of a set

Given: A graph $G$ as in the definition, with $n\ge 2$.

Goal: Show that the displayed minimum is a well-defined real number.

1.1 The admissible subsets form a subset of the finite power set of $V$, so they are finite by [F2]. Since $n\ge 2$, $V$ contains a vertex $v$ and the singleton $\{v\}$ has cardinality $1\le n\mathrm{/}2$; hence the admissible family is nonempty. For each admissible $X$, its positive cardinality makes the quotient $e(X,X^c)\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$ a well-defined real number by [F1] and [F2]. [given, F1, F2, algebra]

2.1 Let $\mathcal{C}$ be the admissible family from step 1.1 and put $m=\mathrm{\mid }\mathcal{C}\mathrm{\mid }\ge 1$. By [F2], a bijection from $\{0,\dots ,m-1\}$ onto $\mathcal{C}$ lists its members as $X_0,\dots ,X_{m-1}$. Set $r_i=e(X_i,X_i^c)\mathrm{/}\mathrm{\mid }{X}_i\mathrm{\mid }$; these are real numbers by step 1.1. The quotient values are exactly $\{r_0,\dots ,r_{m-1}\}$, so the finite-list assertion [F3] gives an attained minimum $q$. Every admissible cut is some $X_i$, hence $q$ is at most every cut ratio and equals one such ratio. It is unique: two such minimum values are each at most the other, and therefore equal. This is the value assigned to $h(G)$, independent of the chosen enumeration. If $n=1$, every nonempty subset is $V$ and has size $1>n\mathrm{/}2$, so the indexing family is empty and the displayed minimum supplies no value. [F2, F3, F4, step 1.1, choose, construct, algebra] ∎

Remark 3.5 of the article names the isometric or Cheeger constant and states a lower bound. It does not display its definition; the unnormalized cut convention above is consistent with the cut estimate in the preceding Lemma 3.4.