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: 

• MA241 Combinatorics

Useful background:

• MA359 Measure Theory
• ST342 Mathematics of Random Events
• ST202 Stochastic Processes

Synergies:

• MA3J2 Combinatorics II
• MA3H2 Markov Processes and Percolation Theory
• MA4J3 Graph Theory

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

Additional Resources