8. M2-Graph Theory

Master of Physics 2016-2017 University of Cergy Pontoise

Introduction to Graph Theory

Lecturer

C Oguey ( oguey @ u-cergy.fr )     CM 18h, TD 12h

The classic branch of graph theory has exploded 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 by itself; 2. give a background to study the active and expanding field of complex systems.

Syllabus

  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

Project report ??%, oral presentation ??%, jury ??%.

Problems

Problem set 1,    set 2

Projects

Write a concise but clear report. 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, similarity, homophily, mixing [N 7.9-7.13]
  8. Percolation [B ch 6, N ch 16]

Other subjects are welcome. Make proposals to lecturer.

C. Oguey, Nov. 2016