Algebraic Graph Theory

• Understand eigenvalues/eigenvectors of graphs and their role in spectral graph theory, e.g., proving bounds on graph parameters
• Apply the spectral decomposition theorem to prove graph theoretic results
• Apply semidefinite programming techniques to prove results about the Lovasz theta function, e.g., that it bounds the Shannon capacity
• Prove standard results about coherent algebras and association schemes
• Prove and apply the Erdos-Ko-Rado theorem
• Use linear algebra and group theory to prove results about graph homomorphisms
• Apply the Weisfeiler-Leman algorithm
• Understand the characterization of graphs with minimum eigenvalue at least -2
• Prove results in fractional graph theory, e.g., about fractional colorings and fractional isomorphisms

1. Eigenvalues and eigenvectors of graphs
2. Graph homomorphisms
3. Applications of linear and semidefinite programming to graph theory
4. Erdos-Ko-Rado Theorem
5. Graph automorphisms
6. Fractional graph theory
7. Shannon capacity and the Lovasz theta function

• 36 – 49 (Tues 13-17)

01227, Mathematical maturity

Two hours of lecture followed by two hours of group work
exercises.