Skip to main content Skip to navigation

MA6M8 Theory of Random Graphs

Lecturer: Richard Montgomery

Term(s): Term 1

Commitment: 30 one hour lectures

Assessment: 100% Oral Exam

Formal registration prerequisites: None

Content:

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

Aims:

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

Objectives:

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

 Books:

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