Graph Theory
A.Y. 2025/2026
Learning objectives
Graphs are fundamental mathematical structures used to model pairwise relations between objects. This course covers some basic concepts of graph theory including cycles, matchings, colorings, connectivity, and extremal graphs. The second part of the course introduces some more advanced topics, such as random graphs and spectral graph theory, that have recently had a remarkable impact on computer science.
Expected learning outcomes
Upon completion of the course, students will be able to: (1) Prove the main theorems of structural graph theory; (2) understand the fundamental properties of some families of random graphs; (3) describe the main spectral quantities related to graphs and show how they can be used in algorithms. These objectives will be assessed via an oral discussion whose evaluation will determine the final grade.
Lesson period: Second four month period
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
Second four month period
Course syllabus
Basic Concepts: Degrees and neighborhoods, notions of connectivity, walks and paths, Eulerian and Hamiltonian paths.
Colorings: Chromatic numbers, cliques, clique number, independent sets, dominating sets.
Random Graphs: Erdős-Rényi graphs and their clique number, and the probabilistic method.
Linear Algebra Review: Elements of linear algebra relevant to spectral graph theory.
Spectral Graph Theory: Fundamental matrices associated with graphs, eigenvalues, eigenvectors, conductance, Cheeger's inequality, and spectral clustering of graphs.
Planted Clique Problem: Definition and algorithms for detecting planted cliques.
Random Walks on Graphs: Transition matrix, convergence, stationary distribution, and mixing time.
Stochastic Block Models: Perturbation theory and block recovery.
Colorings: Chromatic numbers, cliques, clique number, independent sets, dominating sets.
Random Graphs: Erdős-Rényi graphs and their clique number, and the probabilistic method.
Linear Algebra Review: Elements of linear algebra relevant to spectral graph theory.
Spectral Graph Theory: Fundamental matrices associated with graphs, eigenvalues, eigenvectors, conductance, Cheeger's inequality, and spectral clustering of graphs.
Planted Clique Problem: Definition and algorithms for detecting planted cliques.
Random Walks on Graphs: Transition matrix, convergence, stationary distribution, and mixing time.
Stochastic Block Models: Perturbation theory and block recovery.
Prerequisites for admission
A solid understanding of the fundamental concepts of continuous mathematics (calculus) and discrete mathematics (combinatorics), as well as of theoretical computer science (algorithms, complexity).
Teaching methods
Frontal lessons with the aid of blackboard and slides.
Teaching Resources
· Reinhard Diestel, Graph Theory (5th edition), Springer, 2017.
· Handouts provided by the lecturer.
· Handouts provided by the lecturer.
Assessment methods and Criteria
Oral examination.
Professor(s)