Lecture 2. Topics：Many examples of graphs and their Laplacians

http://iwi.tc/wiki/index.php?cmd=read&page=%E8%AC%9B%E7%BE%A9%2FSpecral%20Graph%20Theory%20and%20its%20Applications%2F02.%20Topics%EF%BC%9AMany%20examples%20of%20graphs%20and%20their%20Laplacians

The Laplacian, again [#k6f8e5c0]

  • $x^T L_G x = \sum_{(u, v) \in E} (x_u - x_v)^2$
    • よって任意のグラフについて $L_G$ は半正定値！
  • Lemma 2.1.1. 連結なら $\lambda_2 > 0$
    • 非連結なら 0 になる → Fielder value が連結性という話に再び
  • Corollary 2.1.2. 固有値の 0 の個数が連結成分の数

Some Fundamental Graphs [#p07cc704]

  • $K_n, P_n, R_n$, grid
Product of Graphs [#y55edbe6]

grid にはこれがつかえる

Bounding Eigenvalues [#l0f67e0e]

単純なやつには正確に計算できるが，実際にはわかんないのでboundする

Theorem 2.3.1. [#pa32500b]

min-max ほげ，max-min ほげ．以下の書き方のほうがわかりやすい気がする（Spectral Drawingのやつに乗っていた）．

min 版 [#u9b9acf1]

$A$：対称行列．$k$ 番目に小さい固有値 $\lambda_k$ に対応する $k$ 本目の固有ベクトル $v_k$ は，以下の最適化問題の解である．

  • $\min_{x} x^T A x$
  • subject to: $x^T v_i = 0$ ($i < k$), $x^T x = 1$
    • しかも，$\lambda_k = \min_{x} x^T A x$

特に，グラフラプラシアンでは，1 本目 $v_1 = \boldsymbol{1}$ なので，

  • $\lambda_2 = \min_{x \perp \boldsymbol{1}, x^T x = 1} x^T A x$ または
  • $\lambda_2 = \min_{x \perp \boldsymbol{1}} \frac{x^T A x}{x^T x} $ または
max 版 [#v36bd3b8]

$A$：対称行列．$k$ 番目に小さい固有値 $\lambda_k$ に対応する $k$ 本目の固有ベクトル $v_k$ は，以下の最適化問題の解である．

  • $\max_{x} x^T A x$
  • subject to: $x^T v_i = 0$ ($i > k$), $x^T x = 1$
    • しかも，$\lambda_k = \max_{x} x^T A x$
Lemma 2.3.3. [#geec76c8]
  • $\lambda_{\max}(G) \leq d + 1$
  • これは tight