Graph Theory
A.Y. 2023/2024
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 semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Course syllabus
1. Basic results.
2. Colorings, cliques, independent sets, and dominating sets.
3. Random graphs and the probabilistic method.
3. Spectral analysis.
4. Random walks.
5. Graph clustering.
6. Expanders
2. Colorings, cliques, independent sets, and dominating sets.
3. Random graphs and the probabilistic method.
3. Spectral analysis.
4. Random walks.
5. Graph clustering.
6. Expanders
Prerequisites for admission
Probability theory and statistics. Linear algebra.
Teaching methods
Lecture-style instruction.
Teaching Resources
Lecture notes.
Assessment methods and Criteria
Oral exam based on a grading scale from 1 to 30.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Cesa Bianchi Nicolo' Antonio
Professor(s)