7. M2-Graph Theory

Master of Physics CY University

Introduction to Graph Theory

Lecturer

C Oguey ( oguey @ cyu.fr )     CM 15h, TD 15h

The classic branch of graph theory has seen a revolution in the last decades stimulated by the emergence of internet, social networks, world-wide trading and analogous multi-scale phenomena. The goal of the course is double: 1. provide an introduction to Graph Theory as a beautiful interdisciplinary science in itself; 2. give a background to study the active field of complex systems.

Syllabus

Chapters chosen among:

  1. Fundamentals

  2. Paths, cycles and trees

  3. Hamilton cycles & Euler circuits

  4. Planar graphs

  5. Electrical networks

  6. Vector spaces & matrices associated with graphs

  7. Flows, connectivity, matching

  8. Random graphs, generating functions

References

Grades

Based on projects (written report + oral presentation) and/or final exam. Assessment to be defined.

Problems

Problem    set 1,    set 2

Projects

Write a concise but clear report, at most 8 pages. There will also be an oral presentation.




  Date dueSubject



Project 1tba Individual



Oral tba



Exam tba



Subjects for studies

  1. Colouring [B ch 5]

  2. Groups: Cayley, Schreier diagrams [B ch 8]

  3. Adjacency matrix and Laplacian [B ch 8, N 6.13]

  4. Random walks [B ch 9, N 6.14]

  5. Knots and links [B ch 10]

  6. Centrality, ranking, closeness, cliques, k-plexes, k-cores [N 7.1-7.8]

  7. Transitivity, clustering, reciprocity, …[N 7.9-7.13]

  8. Percolation [B ch 6, N ch 16]

Other subjects are welcome. Make proposals to lecturer.

C. Oguey, Oct. 2023