Lecture on Random Graphs

Sommersemester 2025, TU Berlin

Content:

In the last two decades it has been established that many interesting and important real-world phenomena can be modelled via networks. Put differently, networks serve as a tool to roughly model the basic structure of rather complex situations. Mathematically speaken, networks are graphs, in which the vertices are interpreted as individuals or objects, and where edges indicate some form of interaction or communicaion. Examples are:

• Social relations, like friendship (online and/or offline). The vertices are individuals (or social media user) and an edge is established if the individuals are friends,
• technical networks like the internet or telecommunication networks, or
• biological networks, like the brain.

In this course, we will introduce key probabilistic techniques to describe such networks from a mathematical viewpoint and we will present rigorous results, describing their large-scale behaviour.

Topics covered:

• Modelling Complex Networks: Introduction to random graph models, focussing on inhomogeneous random graphs
• Local Limit Structure: Exploration of the limiting behaviour of local neighbourhoods in large random graphs.
• Degree Distribution: Analysis of degree sequences and their impact on network structure.
• Giant Component and Phase Transition: Study of critical thresholds for the emergence of the giant component.

We recomment a background in probability theory.

Lecture information:

The lecture takes place twice a week for the first half of the semester and builds the foundation for a seminar that takes place in the second half. In the seminar, we extend and deepen the topics of the seminar - see below. Participants of both the lecture and the seminar qualify for a thesis (Bachelor and Master) in one of the topics concerning random graphs under the supervision of Prof. Wolfgang König.

• Times:
  • Tuesdays, 08:00-10:00, Room MA544 (Math building, Straße des 17. Juni 136, 10623 Berlin)
  • Thursdays, 80:00-10:00, Room EW 217 (Eugene-Paul-Wigner-Building, Hardenbergstraße 36)
• Assessment: Oral exams
• Language: English

Contact information:

Dr. Lukas Lüchtrath, luechtrath (at) wias-berlin.de

Dr. Elena Magnanini, Magnanini (at) wias-berlin.de

References

• All main topics are described in detail in R. van der Hofstad - Random Graphs and Complex Networks, Volume II (2024), Cambridge Series in Statistical and Probabilistic Mathematics.
• Lecture notes will be made available.

Seminar Random Graphs

The seminar builds on the lecture and more further important results are about random graphs are presented by student talks. Deepending on the number of participants, we will meet up to twice per week for the second half of the semester. Detailed planning will be made together with the participants during the first half of the semester.

Pleas note that only students who attended the lecture can participate the seminar.

Potential topics for student talks:

• TBA