Lecture 20. Graph Decomposotions

飽きたので Spectral Graph Theory and its Applications は一旦これで終わりにする．

$\phi$-decomposition of $G$: 分割 $V_1, V_2, \ldots, V_k$ such that $\Phi(G[V_i]) \geq \phi$

（conductance とはグラフの切れ無さ的な感じの物．従って，分割後はどの部分グラフもそこそこ切れない感じの分割ということである．）

$(1/\log n)$-decomposition であって，$|\partial(V_1, \ldots, V_k)| \geq |E|/2$ であるものが存在する！

$\phi \leq \Phi(G)$，$S \subset V$ は， $|S| \leq |V|/2$ and $\Phi(S) \leq \phi$ を満たす最大の集合．

もし $|S| < |V|/4$ なら，$\Phi(G[\overline{S}]) \geq \phi/3$．

$\phi$ の値はあとで決めるある定数とする．

再帰的に分割してゆく．$\Phi(G) = \Phi(S)$ としよう．

$Phi(S) > \phi$ なら終わり．
$vol(S) < vol(V) / 4$ なら，$\Phi(\overline{S}) \geq \phi/3$ なので，$S$ のみ再帰．$\overline{S}$ は終わり．
そうでないなら，$S$ も $\overline{S}$ も再帰．

こうすると，一段潜る度に集合の大きさが 3/4 倍にはなる．従って，$\log_{4/3} vol(V)$ 段で済む！

（しかしアルゴリズム的には $S$ が計算できないからくそぽよなんでは……）