3 Isoperimetric problems
For two sets of vertices \(A\) and \(B\), \(E(A, B)\) denotes the set of edges with one endpoint in \(A\) and one endpoint in \(B\).
For any set of vertices \(S\), the edge boundary of \(S\) is equal to the edge boundary of its complement:
The edge boundary of a set \(S\) is equal to the edge connection between \(S\) and \(S^c\):
For a vertex set \(S\), we define \(h_G(S)\) as the ratio of the size of its edge boundary to the minimum volume of \(S\) and its complement:
The Cheeger constant of a graph \(G\), denoted \(h_G\), is defined as the minimum of \(h_G(S)\) for every set of vertices \(S\) with non-zero volume and co-volume:
For any set of vertices \(S\) satisfying \(\operatorname {vol}(S) \le \operatorname {vol}(S^c)\) and \(0 {\lt} \min (\operatorname {vol}(S), \operatorname {vol}(S^c))\), we have:
A graph \(G\) is connected if and only if its Cheeger constant is strictly positive:
We derive a simple upper bound for the first non-trivial eigenvalue \(\lambda _1\) in terms of the Cheeger constant of a connected graph: