[Graph Theory] Spectrum of Graph
선형대수와 그래프 이론을 요렇게 조렇게 막 섞어서 다양한 성질을 살펴보자.
왜냐하면, graph 는 finite vertices 의 binary relation 이기 때문이다.
Definition.
The adjacency matrix <n by n>
$A_{i, j} = \begin{cases}1 & \textit{ if } ij \in E(G) \\ 0 & \textit{otherwise} \end{cases}$
i랑 j 가 edge로 이어졌니?
The incidence matrix <n by $e(G)$>
$B_{i,e} = \begin{cases}1 & \textit{ if } i \in e \\ 0 & \textit{otherwise} \end{cases}$
vertex $i$ 가 edge $j$ 안에 들어가있니? <그러니까, hypergraph 면 이게 여러개고, 그냥 graph면 한 column 에 1이 2개>
Degree matrix <n by n>
$D_{i,j} = \begin{cases}d_G(i) & \textit{ if } i = j \\ 0 & \textit{otherwise} \end{cases}$
vertex $i$ 의 degree를 기록한 diagonal matrix
Laplacian matrix <n by n>
$D_G - A_G$, 그러니까 degree 는 남겨두고, edge가 있으면 -1 을 기록하는 matrix
Fact.
$A_G$ 랑 $L_G$ 는 real symmetric square matrix
그러니까 얘들의 eigenvalues 도 real, diagonalizable 하고, orthinormal basis of eigenvectors 가 있다.
그리고, $L_G$ 의 각 row의 합은 0이다
Theorem <Spectral theorem>
$M$ 이 n by n real symmetric matrix 라고 할 때,
$M$ 은 real eigenvalues $\mu_1 \geq ... \geq \mu_n$ 을 가지고,
n 개의 mutually orthogonal unit eigenvectors $\mathbf{u}_1, ..., \mathbf{u}_n$ , 그것도 $M\mathbf {u}_i = \mu_i \mathbf{u}_i$ 를 가진다.
$A_G$ 의 eigenvalues 인 $\mu_1 \geq ... \geq \mu_n$이 있고, 여기에 대응하는 $\mathbf{u}^1, ..., \ mathbf{u}^n$
$L_G$ 의 eigenvalues 인 $\lambda_1 \leq ... \leq \lambda_n$이 있고, 여기에 대응하는 $\mathbf{v}^1, ..., \mathbf{v}^n$ 이 있다고 치자.
$L_G\mathbf{1}=0$ 이니까, 가장 작은 eigenvalue $\lambda_1$ 은 0이라는 뜻이다.
graph $G$ 가 d-regular라면, Laplacian $L$ 의 eigenvalues 는 $d-\mu_1 \leq ... \leq d-\mu_n$ 이 된다. $0 = \lambda_1 \leq ... \leq \lambda_n$ 이나 $\mu_1 \geq ... \geq \mu_n$ 을 우리는 spectrum of the graph $G$.
eigenvalue 를 사용한 matrix decomposition 을 adjacency matrix 나 laplacian matrix 에 적용했다고 생각하면 된다.
$L_G$의 unit eigenvector $\mathbf{v}$ 랑 eigenvalue $\lambda$를 고려해보면,
$\lambda \parallel \mathbf{v} \parallel ^2 = \mathbf{v}^T \lambda \mathbf{v} = \mathbf{v}^T \L_G \mathbf{v} = \sum_{ij \in E(G)} A_{i,j}(\mathbf{v}(i) - \mathbf{v}(j))^2 \geq 0$
여기서 잠깐 $\mathbf{1}_S = \begin{cases} 1 & \textit{ if } i \in S \\ 0 \textit{otherwose} \end{cases}$ 로 정의해놓고,
two sets $S, T \subseteq V(G)$ 에서, $e(S,T) = e_G(S, T)$ 로 $S, T$사이의 edge 갯수를 표현해보자. $S \cap T$ 는 두 번 세진다.
Proposition
$\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ 이고, $\mathbf{x}^T A_G \mathbf{y} = \sum_{ij \in E(G)\mathbf{x}_i \mathbf{y}_j$ 이고, $S_1, S_2 \subseteq [n]$ 이라고 했을 때,
$e(S_1, S_2) = \mathbf{1}_{S_1}^T A_G \mathbf{1}_{S_2}$
Definition
Rayleigh quotient: $\frac{\mathbf{x}^T M \mathbf{x}}{\mathbf{x}^T \mathbf{x}} $
어차피 $M \mathbf{x}$ 가 $\mathbf{x}$ 를 mapping 해주는 거라면, $m$ 은 얼마나 expand 해주는가? 사실 이건 또 eigenvalue 와 연관있는 거라구.
Theorem <Courant-Fischer>
$M$ 은 real symmetric matrix 고, eigenvalues $\alpha_1 \geq ... \geq \alpha_n$ 이라 치자.
$\alpha_k = max_{S \subseteq \mathbb{R}^n, dim(S) = k} min_{\mathbb{x} \in S-\{0\} }\frac{\mathbf{x} M \mathbf{x}}{ \mathbf{x} \mathbf{x} } = min_{S \subseteq \mathbb{R}^n, dim(S) = n-k+1} max_{\mathbb{x} \in S-\{0\} }\frac{\mathbf{x}^T M \mathbf{x}}{ \mathbf{x} \mathbf{x} } $
이걸 좀 더 쉽게 가면, $\lambda_min = minR(M, x), \lambda_max = max R(M, x)$. 어쨌건 저 Rayleigh quotient 는 $x$ 가 symmetrical matrix $M$ 에 의해 확장될 수 있는 범위를 의미하는 거고, 이게 곧 eigen value 인건데, 이게 가장 적을 때에는 minimum eigenvalue, 즉 $\lambda_1$이 되고, 이게 가장 클 때에는 maximum eigenvalue, $\lambda_n$ 이 되는 거다. 그리고 $L_G$ 는 semifinite positive 니까 $\lambda_1$이 0보다 커져서 모두 양수가 되는 거고.
12.1 Avergae degree and connectivity
Indicator vector $\mathbf{1}_X$에 대해서, Rayleigh quotient $\frac{\mathbf{1}_X^T A_G \mathbf{1}_X}{ \mathbf{1}_X^T \mathbf{1}_X }$ 는 $X$ 안의 number of edges 를 의미한다.
Lemma
$d(G) \leq \mu_1 \leq \Delta(G)$
adjacency matrix 의 첫번째, 가장 큰 eigenvalue 는 degree 갯수 안쪽으로 떨어진다.
$\textit{Proof}$
$\mu_1 = max_{\mathbf{x}} \frac{ \mathbf{x}^T A_G \mathbf{x} }{ \mathbf{x} \mathbf{x} } \geq \frac{ \mathbf{1}^T A_G \mathbf{1} }{ \mathbf{1}^T \mathbf{1} } = \frac{\sum_i d(i)}{n} = d(G)$
$\mu_1 = \farc{(A_G \mathbf{\mu^1})_i}{\mathbf{\mu}_i^1} = \frac{\sum_{j \in N_G(i)} \mathbf{\mu}_j^1}{ \mathbf{\mu}_i^1 } \leq \sum_{j \in N_G(i)} A_{i,j} = d(i) \leq \Delta(G)$
Lemma
$G$ 가 connected이고, $\mu_1 = \Delta(G)$라면, $G$ 는 regular graph
connected 에서 adj. matrix 의 최대 eigenvalue 가 $\Delta(G)$면, $G$는 regular다.
Theorem <Cauchy's interlacing theorem>
$A$ 가 n by n real sysmmetric matrix 고, $B$ 가 dimension n-1 짜리 principal submatrix of $A$ 라면 <B 가 A에서 같은 자리의 row 나 column 을 빼서 만들어졌다면>
$\alpha_a \geq \beta_1 \geq \alpha_2 \geq \beta_2 \geq ... \geq \beta_{n-1} \geq \alpha_n$
$\alpha$랑 $\beta$ 는 A, B의 eigenvalues
이 얘기는, 우리가 vertex를 하나 날리면 average degree는 높아질지 몰라도 largest eigenvalue 는 절대 증가하지 않는다는 뜻. 실제로 $G$의 어떤 subset을 잡아도 걔의 평균 degree 는 원래 그래프의 largest eigenvalue 보다는 커질 수가 없고, largest eigenvalue 의 lower bound 를 준다.
Theorem
$\chi(G) \leq \lfloor \mu_1 \rfloor +1$
$\textit{Proof}$
induction on the number of vertices. vertex 1일때는 쉽고, 일단 $d(G) \leq \mu_1$ 인건 우리가 알고. $S = V - \{i\}$ 라고 하면, Cauchy's interlacing theorem 을 하면 $G[S]$ 는 최대로 큰 eigenvalue 를 가져도 $\mu_1$ 이고, induction 으로 $\lfloor \mu_1 \rfloor +1$-colorable 이라는 걸 알게되지.
이렇듯, eigenvaector 는, 그리고 그것이 양수라는 것은 많은 정보를 주지.
Theorem <Perron-Frobenius theorem>
$G$ 는 connected graph, $\mu_1 \geq ... \geq mu_n$ 이 $A_G$ 의 eigenvalues 라고 하자. 그리고 $\mu_1$ 이 strictly positive eigenvector라고 하자.
$\mu_1 \geq -\mu_n$ and $\mu_1 > \mu_2$.
connected graph 에서는 $\mu_1 > \mu_2$ 가 성립한다.
Lemma
$L_G$의 eigenvalues $0 = \lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n$가 성립할 떄
$\lambda_2 > 0 \Leftrightarrow G$ is connected
$\textit{Proof}$
If $G$ is disconnected, then
$L = \begin{pmatrix} L_{G_1} & 0 \\ 0 & L_{G_2} \end{pmatrix}$
$G_1, G_2$에 대해서 우리는 two eigenvectors $\begin{pmatrix} \mathbf{1} \\ 0 \end{pmatrix}$, $\begin{pmatrix} 0 \\ \mathbf{1} \end{pmatrix}$ 이 eigenvalue 0에 대해 성립.
$G$ 가 connected라면, $\mathbf{x}$ 는 eigenvalue 0 인 $L$ 의 eigenvector 이므로
$\mathbf{x} L \mathbf{x} = \sum_{ij \in E(G)} (\mathbf{x}_i - \mathbf{x}_j)^2 = 0$니까,
$\mathbf{x}_i = \mathbf{x}_j$ 라는 얘기. $G$ 가 connected 니까 $\mathbf{x}$ 는 모든 i, j에 대해서 같아서 constant vector 고, eigenvalue 0 에 의한 eigenspace 는 dimension 1이다.
12.2. Walks and Cliques in graphs
Proposition
$(A^k)_{i, j}$ 는 $i$ 부터 $j$ 로 가는 length $k$ 짜리 walks의 갯수다.
Proposition
$i, j \in [n]$ 에 대해서 $c_1, ..., c_n \in \mathbb{R}$ 이면 $k \geq 1$에 대해
$A_{i, j}^k = \sum_l^n c_l \mu_l^k$
Theorem
$G$ is bipartite $\Leftrightarrow$ its spectrum $\mu_1 \geq ... \geq \mu_n$ is symmetric about zero
그러니까, $\mu_1 = -\mu_n, \mu_2 = -\mu_{n-1} ...$ 인거.
Theorem <Motzkin-Straus>
$\omega(G) = r$이라고 하자.
$maximum of $\sum_{ij \in E(G)} \mathbf{x}_i \mathbf{x}_j$ over all nonnegative vector $\mathbf{x}$ with $\sum_i \mathbf{x}_i = 1$ is $\frac{1}{2}(1-\frac{1}{r})$
12.3. Independent sets and the chromatic number
Theorem <Hoffman's bound>
$G$ 가 d-regular graph 이고, $\mu_n$ 이 smallest eigenvalue of $A_G$ 일 때,
$\alpha(G) \leq \frac{-\mu_n n}{d-\mu_n}$
이걸 non-regular graph 로 generalize 하는 건,
Theorem <Godsil, Newman>
$S$ 가 $G$의 independent set이라고 하고, $d_{av}(S)$ 가 $S$ 의 average degree 라고 하면
$|S| \leq n(a - \frac{ d_{av}(S )}{\lambda_n})$
Theorem.
$\chi(G) \geq 1 + \frac{\mu_1}{-\mu_n}
Proposition
$A = \begin{pmatrix} B & C \\ C^T & D \end{pmatrix} $ be a symmetric matrix. Then we have
$\lambda_{max}(A) \leq \lambda_{max}(B) + \lambda_{max}(D)
Lemma 12.23
For the block-partitioned symmetric matrix with $k \geq 2$, then
$(k-1) \lambda_{min} (M) + \lambda_{max}(M) \leq \sum_i \lambda_{max}(M_{i, i})$
12.4. The number of spanning trees
Theorem <Matrix-Tree theorem>
The number of spanning trees in a connected graph $G$ on the vertex set $[n]$ is
$det L_i(G) = \frac{1}{n}\lambda_2 ... \lambda_n$ for any $i \in [n]$, where $e = 0 \leq \lamdba_1 \leq ... \leq \lambda_n$ are the eigenvalues of $L_G$.
Proposition <Binet-Cauchy formula>
A 와 B 가 각각 m by n, n by m matrix, m<n 이면
$\det AB = \sum_{S \in \binom{n}{m}} \det A[S] \det B[S]$ where $A[S]$ 는 $S$에 안들어간 index 를 column 들을 지운 $A$ <m by m>, $B[S]$ 는 $S$에 들어간 index의 row 들을 지운 <m by m> matrix.
$B(i)B(i)^T = L_i (G)$
Claim.
$S$ 가 $n-1$ 개의 edgeset 이라면,
$det B(i)[S] = \begin{cases} \pm 1 & \textit{if S is a spanning tree} \\ 0 & \textit{otherwise} \end{cases}
이젠 설명도 없음 ㄷㄷ