Graph Theory

author: Rémi Monasson, National Center for Scientific Research (CNRS)
published: Nov. 21, 2013,   recorded: September 2013,   views: 6752


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 56:02
Watch Part 2
Part 2 58:43
Watch Part 3
Part 3 1:04:42
Watch Part 4
Part 4 59:34
Watch Part 5
Part 5 56:22
Watch Part 6
Part 6 47:23


Random graphs are of central importance in probability theory, combinatorics, and statistical physics. The purpose of these lectures is to review, in a non-rigorous manner, the typical properties of random graphs, with a strong emphasis on the Erdos-Renyi ensemble. We will illustrate those properties, and in particular the percolation transition, on the special case of random systems of Boolean equations. Statistical mechanics techniques will be introduced to study rare properties, that is, large deviations from the typical case. In the second lecture we will focus on dynamical processes modifying random graph structures, and analyze their evolution. Furthermore the replica method for 'dilute' systems will be presented. Finally, in the third lecture, random spatial maps will be considered, in relationship with the modeling of recent experiments in neurobiology.

Suggestions for further readings:

  • B. Bollobas, Random Graphs, Cambridge University Press (2001)
  • N.C. Wormald, The differential equation method for random graph processes and greedy algorithms, in Lectures on Approximation and Randomized Algorithms (M. Karonski and H.J. Proemel, eds), pp. 73-155. PWN, Warsaw (1999)
  • D.J. Amit, Modeling Brain Function: The World of Attractor Neural Networks, Cambridge University Press (1992)
  • for more on statistical mechanics and random Boolean systems, see R. Monasson, Introduction to Phase Transitions in Random Optimization Problems, Lecture Notes of Les Houches Summer School, Elsevier (2006) and references therein.

See Also:

Download slides icon Download slides: netadis2013_monasson_graph_theory.pdf (4.9 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 coora, January 24, 2023 at 6:05 p.m.:

In football, the main defender's job is to prevent the opposing team's attack from scoring, but as we will learn in this article, you are also required to do more tasks that affect the team's performance
From your position that exposes the entire field from your goal to the opponent's goal, which was shown here on it link here website long time ago.

Write your own review or comment:

make sure you have javascript enabled or clear this field: