240169 Random Graphs (VÜA) (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.

Requirements for participation, required level

• A working knowledge of the fundamentals of probability theory (in particular probability distributions, random variables, expectation/moments of random variables) is essential.
• Knowledge of advanced concepts of probability theory (convergence of random variables, limit theorems, conditional distribution and expectation) is desirable.
• No prior knowledge of graph theory is required. The relevant graph theoretical concepts will be introduced in the lecture.

---

Module combinations for pre-2025 Mathematik Master
This course may be combined with Prof. Ellen Baake's Stochastische Modelle in der Biologie (https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=567940092) this term or Prof. Ellen Baake's Mathematische Biologie next summer term to complete the module 24-M-P1a or 24-M-P1b. Alternative arrangements may be possible upon request. Just get in touch!

In the new Mathematics Master study programme this course along with its final exam can stand on its own as 24-M-PT-ST5a or 24-M-PT-ST5b.

Bibliography

The course will draw heavily from Remco van der Hofstad’s excellent book Random Graphs and Complex Networks. Vol. 1. The book is available for free from the author’s website (https://www.win.tue.nl/~rhofstad/NotesRGCN.pdf) and was also published by Cambridge University Press (https://doi.org/10.1017/9781316779422).