8. M2Graph Theory
Master of Physics 20162017 — University of Cergy Pontoise
Introduction to Graph Theory
Lecturer
C Oguey ( oguey @ ucergy.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, worldwide trading and analogous
multiscale 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
 Fundamentals
 Paths, cycles and trees
 Hamilton cycles & Euler circuits
 Planar graphs
 Electrical networks
 Vector spaces & matrices associated with graphs
 Flows, connectivity, matching
 Random graphs, generating functions
References
 B Bollobas, Modern Graph Theory, Springer 1998
 R Diestel, Graph Theory, Springer 2010, diestelgraphtheory.com
 M Newman, Networks: an Introduction, Oxford UP 2003
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 due  Subject 



Project 1  tba  Individual 



Oral  tba 



Exam  tba 




Subjects for studies
 Colouring [B ch 5]
 Groups: Cayley, Schreier diagrams [B ch 8]
 Adjacency matrix and Laplacian [B ch 8, N 6.13]
 Random walks [B ch 9, N 6.14]
 Knots and links [B ch 10]
 Centrality, ranking, closeness, cliques, kplexes, kcores [N 7.17.8]
 Transitivity, clustering, reciprocity, similarity, homophily, mixing [N
7.97.13]
 Percolation [B ch 6, N ch 16]
Other subjects are welcome. Make proposals to lecturer.
C. Oguey, Nov. 2016