MA6M8 Theory of Random Graphs
Lecturer: Richard Montgomery
Term(s): Term 2
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