Graph Theory

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.

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.