Combinatorial graphs and networks appear in many theoretical and
practical contexts. It is beneficial for every working mathematician
and theoretical computer scientist to have a good familiarity with
these concepts. A very active research area is spectral graph theory,
where graphs and their properties are studied via the eigenvalues of
their associated adjacency matrices. This topic is particularly
appealing since it needs very little background knowledge and leads
efficiently to many beautiful and deep observations and results. We
will cover various useful aspects of general interest with a geometric
viewpoint, amongst them: variational characterisation of eigenvalues,
Cheeger isoperimetric constants or expansion rates and inequalities
between them and eigenvalues, leading to the timely topics of expander
graphs, spectral clustering, construction of codes, Ramanujan graphs,
and Cayley graphs as geometric representations of discrete groups. We
will discuss fundamental connections between eigenvalues and dynamics
like mixing properties of random walks and electrical networks. We
will study eigenvalue relations under graph constructions like
coverings, zigzag products, and line graphs, and we will also
investigate the interplay between eigenvalues and specific discrete
curvature notions (like one based on optimal transport). In summary,
the course provides a variety of interesting tools which can be used
to study graphs and networks both from a geometric and an algebraic
viewpoint via eigenvalues.
The course will be self contained. Only basic knowledge in linear
algebra (linear maps, symmetric matrices, eigenvalues), graph theory
(vertices and edges of graphs, graph automorphisms), algebra (discrete
groups and generators, symmetry groups), and probability theory
(discrete probability spaces) is needed.
Lecture 1: The Adjacency Matrix (simple graphs, adjacency matrices, (adjacency) eigenvalues and spectrum)
Lecture 2: More about the adjacency matrix (induced subgraphs, interlacing, diameter, line graphs)
Lecture 3: Laplacian and Cheeger constant (nonnormalized Laplacian, variational characterisation of eigenvalues, Rayleigh Quotients, Cheeger (isoperimetric) constants, expanders, Cheeger inequality)
Lecture 4: Cheeger Inequality and Spectral Clustering (Cheeger Inequality and Spectral Geometry, Co-Area Formula, Spectral Clustering and k-means algorithm, higher order Cheeger constants and inequalities)
Lecture 5: Ramanujan graphs and Lubotzky-Phillips-Sarnak Construction (Alon-Boppana, Ramanujan Graphs, Cayley Graphs, Lubotzky-Phillips-Sarnak Construction)
Lecture 6: Lifts, signatures, and the Bilu-Linial Conjecture (Lifts and covering maps, signatures and associated lifts and signed adjacency matrices, switching equivalence and balanced signatures, old and new eigenvalues of a lift, matching polynomials, common interlacings)
Lecture 7: Logarithmic diameter of expanders, random walks, and the Dirichlet problem (upper diameter estimate for graphs with positive Cheeger constants, application to abelian Cayley graphs, Expander Mixing Lemma, random walks and transition probabilities, Random Walk Laplacian, harmonicity, simple random walks, Maximum Principle, Dirichlet Energy)
Lecture 8: Random walks and electric networks (escape probabilities, electrical networks, voltages, currents, resistances, conductances, energy dissipation, Kirchhoff cycle rule (KCR), Kirchhoff vertex rule (KVR), effective resistance, simple random walk, stationary distribution, mixing rate)
Lecture 9: Zig-zag Products and asymptotically good error correcting codes (Replacement and Zig-zag product, codewords and binary codes, Hamming distance, Hamming balls, minimal (relative) distance, rate, asymptotically good codes, linear codes, redundency, Gilbert-Varshamov and sphere packing bounds, graph code)
Lecture 10: Ollivier Ricci-curvature on graphs (Background information from Riemannian Geometry, (optimal) transport plans, costs, Wasserstein distance, Duality, (otpimal) Kantorovich potentials, Ollivier Ricci-curvature, Discrete Bonnet-Myers Theorem, Discrete Lichnerowicz Theorem)