Home   About me   Education Experience     Teaching   Publications   Supervision   Contact   Miscellaneous

MA5510 - Spectral Graph Theory

Topics covered

Week Contents
Week 1 Adjacency matrices of Graphs: Basic properties and computing eigenvalues of some graphs. Perron-Frobenius theorem. Eigenvalues, eigenvectors and bipartiteness.
Week 2 Harary's determinant formula, Sach's coefficient theorem and applications.
Week 3 and 4 Inverse of tree: Characterization of invertibility, formula for the inverse of the trees, alternating path, corona tree, characterization of trees whose inverse is also a tree.
Week 5 and 6 Spectral Theorem for symmetric matrices, Rayleigh quotient theorem. Bounds for the eigenvalues. Wilf's theorem, Hoffman's bound, Stanley's bound, Hong's bound, Nikiforov's bound. Mantel's theorem and Nosal's theorem.
Week 7 Moore graphs, Hoffman-Singleton Theorem. Decomposition of K10 into Petersen graphs. Witsenhausen Theorem and Graham-Pollak Theorem. Strongly regular graphs.
Week 8 The friendship theorem. Expander mixing lemma and Hoffman radio bound. Courant-Fischer Theorem. Cauchy interlacing theorem, Poincare separation theorem.
Week 9 Applications of interlacing theorems: Cvetkovic Inertia Bound. Proof of sensitivity conjecture. Graphs determined by spectrum, construction cospectral graphs.
Week 10 and 11 Laplacian matrices and incidence matrices. Spectral bounds for Max-cut and bisection problems. Matrix-Forest Theorem. Counting the number of spanning trees in Hypercubes.
Week 12 Bounds for the Laplacian eigenvalues. Algebraic connectivity. Fiedler's Nodal domain theorem.
Week 13 Semester Break
Week 14 Characteristic vertices and Charateristic edges of trees. Classification of trees.
Week 15 Monotonicity property of Fiedler vector. Bounds for the algebraic connectivity.
Week 16 and 17 Distance matrices of trees: Determinant and inverse. Eigenvalues of distance matrices and Laplacian matrics. We will discuss some of the results of Graham and Pollak, Graham and Lovasz, and Grone, Merris and Sunder.
  • References:
  • Course description