PhD course - Spectral graph theory and random walks: connections and applications
Abstract
Spectral properties of graphs are of paramount importance. While important properties of graphs are reflected in properties of their spectra, fundamental connections between spectral and topological properties of graphs are at the core of some successful approaches in a number of problems, e.g., graph partitioning or community detection. At the same time, graph spectra are related to key properties of random walks in graphs. These, in turn, describe key aspects of some fundamental dynamics on graphs.
The goal of this course is introducing students to these topics, providing an overview of key notions, some reference applications and how spectral properties of graphs can be investigated from different perspectives, leading to insights into applications of interest both in computer science and other areas of research.
Speakers: Prof. Luca Becchetti (Sapienza University) and Prof. Francesco Pasquale (University Tor Vergata Rome)
Course schedule
Monday, June 12th
9am - 11am. Francesco Pasquale
Introduction to Markov chains and random walks. Examples: birth-and-death chains. Applications: An algorithm for 3-SAT with running time O((4/3)^n \poly(n)).
11am - 1pm. Francesco Pasquale
Random walks, stationary distributions. Irreducibility and aperiodicity, lazy chains. Total variation distance, mixing time. Relaxation time and the second eigenvalue. Mixing and relaxation.
Tuesday, June 13th
10am - 12am noon. Luca Becchetti
Graphs and graph matrices. Spectral theorem for symmetric matrices. Variational characterization of eigenvalues. Graph matrices.
2pm - 4pm. Luca Becchetti
Bottlenecks and cuts. Finding cuts of minimum conductance. Easy part of Cheeger's inequality. Sparse cuts and Laplacian's second eigenvecto's profile: Examples.
Wednesday, June 14th
10am - 12am noon. Francesco Pasquale
Sampling and counting, the Monte Carlo Method. Approximate sampling and approximate counting. Application: DNF-counting. Introduction to the Markov Chain Monte Carlo method.
2pm - 4pm. Luca Becchetti
Hard part of Cheeger's inequality and implications.
Thursday, June 15th
10am - 12am noon. Francesco Pasquale
Techniques for bounding mixing time: coupling, path coupling, bottleneck ratio. Example: Random walk on the hypercube.
2pm - 4pm. Luca Becchetti
Eigenvalues, bottlenecks and rapid mixing. Mixing time and conductance. Expanders and expander mixing lemma.
Friday, June 16th
10am - 12am noon. Francesco Pasquale
The Markov Chain Monte Carlo method. Application: Approximate counting proper colorings.
2pm - 4pm. Luca Becchetti: Spectral Graph Theory
Beyond conductance: graph partitioning and k-way constant. Brief overview of higher-order Cheeger's inequalities. Spectral embeddings and Spectral graph clustering with examples.
Zoom link: https://uniroma1.zoom.us/j/98700192862?pwd=VlRPQmEyQjJUWXdjTzJyMFVDZEVXdz09