[Spectral Graph] Lecture 1 : Introduction and course overview

Yale 의 강의 Spectral Graph Theory(2018 Fall) 자료를 정리한 포스트입니다.

코스 전체에서 다루는 주제입니다.

# Lecture Topic
1 Introduction and course overview
2 Essential spectral theory, Hall’s spectral graph drawing, the Fiedler value
3 Some fundamental graphs, bounding eigenvalues by test vectors
4 Bounding eigenvalues by comparison theorems
5 Cayley graphs
6 High-frequency eigenvalues Independent sets and graph coloring
7 Low-frequency eigenvalues Nodal Domains
8 Testing isomorphism of graphs with distinct eigenvalues
9 Testing isomorphism of strongly regular graphs
10 Random walks on graphs
11 Cheeger’s inequality
12 Phyiscal metaphors for graphs Spring & Electrical networks
13 Elimination and Schur Complements Effective Resistance
14 More effective resistance
15 Tutte embeddings of planar graphs
16 The Fiedler value of planar graphs
17 Properties of expander graphs
18 An elementary construction of expander graphs
19 Pseudo-random generators from expander graphs
20 Andersen’s proof of Cheeger’s inequality using Lovasz-Simonovits
21 Sparsification of graphs by random sampling
22 Linear-sized sparsifiers of graphs
23 Iterative solvers for linear equations
24 Preconditioning and Laplacian equations
25 Bipartite Ramanujan Graphs
26 The matching polynomial of a graph