Algebraic Graph Theory
Technical University of Denmark
General course objectives:
The course will provide students with the mathematical tools for applying
algebraic techniques to graph theoretic questions. The main focus will be applying linear
algebraic tools to matrices associated to graphs in order to reveal graph structure and
information about graph parameters.
Learning objectives:
A student who has met the objectives of the course will be able to:- 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
Contents:
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
Back
|
|
