Skip to main content Skip to navigation

MA4M8 Theory of Random Graphs

Lecturer: Richard Montgomery

Term(s): Term 2

Status for Mathematics students: List C

Commitment: 30 one hour lectures

Assessment: Three hour examination (100%)

Formal registration prerequisites: None

Assumed knowledge: 

Useful background:



The study of Random Graphs combines combinatorial and probabilistic techniques, and has applications in areas from Statistical Physics and Computer Science back to Extremal Combinatorics. In this course, we will study the typical properties of a random graph, with topics including the following:

  • Different random graph models
  • Thresholds for graph properties
  • Applications to Extremal Combinatorics problems via the Probabilistic Method
  • The evolution of random graphs and the emergence of the giant component
  • The chromatic number of a random graph
  • Connectedness and Hamiltonicity in random graphs
  • The appearance of small subgraphs


To give students a good grounding in methods from the theory of random graphs while proving fundamental results in the area.


By the end of the module the student should be able to:

  • State and prove key results presented in the module
  • Adapt the methods to new settings, including using coupling arguments
  • Apply the techniques to determine other likely properties of random graphs


  • Bollobás, B., Random Graphs
  • Janson, S, Luczak, T and Ruciński, A., Random Graphs

Additional Resources