Graph Theory
A.Y. 2026/2027
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
Lecture 1. Basics
Graphs, subgraphs, degrees, paths, cycles, radius, diameter, girth.
Lecture 2. Basics
Connectivity, bipartite graphs, walks, Eulerian circuits, Hamiltonian cycles.
Lecture 3. Invariants
Clique number, independence number, chromatic number, and their elementary relations. Turán's Theorem and its proofs.
Lecture 4. The Erdős-Rényi Model
Clique number, independence number, chromatic number.
Lecture 5. More on Erdős-Rényi
Chromatic number, connectivity. Review of linear algebra and the spectral theorem.
Lecture 6. Symmetric Matrices and Rayleigh Quotients
Cuts and conductance. Graph Laplacian. Cheeger's first inequality.
Lecture 7. Cheeger's Second Inequality
Lecture 8. Exercises
Lecture 9. Planted Clique
Degree-based algorithm. Spectral algorithm.
Lecture 10. Random Walks
Eigenvectors, eigenvalues, and convergence to the stationary distribution.
Lecture 11. Random Walks
Mixing time and the second eigenvalue of the Laplacian.
Lecture 12. Cuts and Flows
Max-flow/min-cut theorem and matching in bipartite graphs. König's Theorem.
Lecture 13/14. Stochastic Block Models
Lecture 15. Extremal Graph Theory and Turán's Theorem
Minors and the Robertson-Seymour theorem. Hadwiger number and chromatic number. Hadwiger's conjecture.
Lecture 16. Exercises
Graphs, subgraphs, degrees, paths, cycles, radius, diameter, girth.
Lecture 2. Basics
Connectivity, bipartite graphs, walks, Eulerian circuits, Hamiltonian cycles.
Lecture 3. Invariants
Clique number, independence number, chromatic number, and their elementary relations. Turán's Theorem and its proofs.
Lecture 4. The Erdős-Rényi Model
Clique number, independence number, chromatic number.
Lecture 5. More on Erdős-Rényi
Chromatic number, connectivity. Review of linear algebra and the spectral theorem.
Lecture 6. Symmetric Matrices and Rayleigh Quotients
Cuts and conductance. Graph Laplacian. Cheeger's first inequality.
Lecture 7. Cheeger's Second Inequality
Lecture 8. Exercises
Lecture 9. Planted Clique
Degree-based algorithm. Spectral algorithm.
Lecture 10. Random Walks
Eigenvectors, eigenvalues, and convergence to the stationary distribution.
Lecture 11. Random Walks
Mixing time and the second eigenvalue of the Laplacian.
Lecture 12. Cuts and Flows
Max-flow/min-cut theorem and matching in bipartite graphs. König's Theorem.
Lecture 13/14. Stochastic Block Models
Lecture 15. Extremal Graph Theory and Turán's Theorem
Minors and the Robertson-Seymour theorem. Hadwiger number and chromatic number. Hadwiger's conjecture.
Lecture 16. Exercises
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 at the blackboard.
Teaching Resources
· Reinhard Diestel, Graph Theory (5th edition), Springer, 2017. ISBN: 978-3-662-53621-6
· Handouts provided by the lecturer.
· Handouts provided by the lecturer.
Assessment methods and Criteria
Oral examination. The exam lasts up to an hour, and consists of a sequence of questions and exercises aimed at assessing the students' preparation and their ability to manipulate the key notions and techniques of the course.
INFO-01/A - Informatics - University credits: 6
Lessons: 48 hours
Professor:
Bressan Marco
Shifts:
Turno
Professor:
Bressan MarcoProfessor(s)