WiSe 2025/2026

Many complex real-world networks (your circle of friends, collaborations between scientists, the internet, web pages on the World Wide Web, interactions between proteins, the structure of your brain, …) can be modelled as graphs – nodes/vertices connected by edges – in a fruitful way. Even the seemigly drastic reduction of complex data to objects that may or may not share some sort of connection can expose interesting properties and phenomena. Interesting real-world networks are often extremely large, which makes them hard to describe in their entirety. One way of making these networks tractable for analysis is to treat them as randomly generated according to local rules. This gives rise to the theory of random graphs.

In this lecture we will discuss the basics of random graph theory, meet some of its models and learn about and prove some typical results.

We will start with the staple model of random graph theory: the Erdős–Rényi random graph. Even though this model is very simple, it already exhibits a number of interesting typical phenomena – most notably abrupt changes in behaviour when a parameter is varied, so-called phase transitions – and the toolbox used for its analysis – coupling techniques, comparison to branching processes, large deviation theory – can be extended to more complex models as well.

We will also introduce other random graph models that try to capture certain aspects of real-world networks better than the simple Erdős–Rényi model, namely inhomogeneous random graphs, the configuration model and preferential attachment models.