Lecture 4. Topics: Cutting graphs and Cheeger's inequality.
Cutting Graphs [#fd9c620a]
ratio of cut $S$ :=
$$
\phi(S) = \frac{e(S, \overline{S})}{\min(|S|, |\overline{S}|)}
$$
isoperimetric number of graph $G$ :=
$$\phi(G) = \min_{S \in V} \phi(S)$$
An integer program [#db890df0]
$$
\phi(G) \geq \lambda_2 / 2
$$
の証明．
- Donnath and Hoffman による $\phi(G)$ を近似する整数計画問題．2 近似．
- これを 0 or 1 → [0, 1] に．
- 式の値は，$x$ の定数倍や定数加算によって変化しない
- なので，実際には制限しなくてよい
- $\sum x_i$ = 0 にするとあら便利．分母が綺麗に．
Cheeger's Inequality [#g4563b02]
$$
\lambda_2 \geq \frac{\phi^2}{2 d_{\max}}
$$
固有ベクトルに限らずより一般に．ベクトル $x \perp \boldsymbol{1}$ があって，WLOG $x_1 \leq x_2 \leq \cdots \leq x_n$ として，ある $i$ があって，
$$
\frac{x^T L x}{x^T x} \geq \frac{\phi(\{1, \ldots, i\})^2}{2d_{\max}}
$$
証明は省略されとった．
左側のやつの最小値をもたらすのが $lambda_2$ だし，そういう時もコレを使えば実際にカットを構成できるってことだな．
