Course Introduction

• Prerequisite：Linear Algebra
• Recommended for： graduate students
• Introduction：

Algebraic Graph Theory is the branch of mathematics that studies graphs by using algebraic properties of associated matrices. More in particular, spectral graph theory studies the relation between graph properties and the spectrum of the adjacency matrix or Laplace matrix. And the theory of association schemes and coherent configurations studies the algebra generated by associated matrices. This course, also called Linear Algebraic Graph Theory, emphasizes on the first part, and another course, called Algebraic Combinatorics, includes the second part.

• Syllabus：

1. Matrices associated to a graph
2. Characteristic polynomial of a graph
3. Spectrum of a graph
4. Perron-Frobenius theorem
5. Interlacing property
6. The Courant-Weyl inequalities
7. Positive semi-definite matrix
8. The number of spanning trees in a graph
9. Spectrum tells regularity and bipartiteness
10. Laplace matrix
11. Laplace eigenvalues and degrees
12. Switching and cospectral graphs
13. Graham-Pollak decomposition theorem (optimal)
14. The spectrum of Cayley graphs (optimal)
15. Selected topics: cliques, cocliques, chromatic number, Shannon capacity, connectivity, separation, diameter bound, perfect matchings, block designs (optional)

• Reference：

1. Andries E. Brouwer and Willem H. Haemers, Spectra of graphs, Electrical Book
2. Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, 2001