Lecture and seminar on Random Graphs

Sommersemester 2025, TU Berlin

Contact information:

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

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

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.

• Times:
  • Lecture: 15.04.--05.06.; Seminar: 10.06.--18.07.
  • Tuesdays, 08:30-10:00, Room MA544 (Math building, Straße des 17. Juni 136, 10623 Berlin)
  • Thursdays, 08:15-09:45, Room EW 217 (Eugene-Paul-Wigner-Building, Hardenbergstraße 36)
• Assessment: Oral exams
• Language: English
• Thesis in this field: 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
• Related lecture: A lecture about Branching Processes also takes place this term. Branching processes and random graphs align well with each other and participants of our lecture may consider visiting the other lecture as well (and vice versa)
• ISIS course: can be found here
• Credit points: 5 CP
• Lecture notes, will constantly be updated throughout ge course. As usually, no guarantee for completeness

Problem Sheets

• Sheet 1

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. The book is accesible online within the TU Berlin network or on the author's personal website.
• Further literature:
  • R. van der Hofstad - Random Graphs and Complex Networks, Volume I (2016), Cambridge Series in Statistical and Probabilistic Mathematics. Also available on the author's personal website.

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 (10.06.--18.07.). Detailed planning will be made together with the participants during the first half of the semester.

• Times:
• Seminar: 10.06.--18.07., except 24.06., 26.06.
• Tuesdays, 08:30-10:00, Room MA544 (Math building, Straße des 17. Juni 136, 10623 Berlin)
• Thursdays, 08:30-10:00, Room EW 217 (Eugene-Paul-Wigner-Building, Hardenbergstraße 36)
• Requirement: Attending the lecture before
• Format: Each participant gives a talk of 60-75 mins and writes a short summary up to 3 pages about another talk
• Talk assignment: Second week of the semester after the lecture. There are 8 Talks available.

Topics for student talks:

• Almost locality of the giant component (Chapter 2.6)
• Small-world character of inhomogeneous random graphs (Chapter 6, 3 talks)
• Graph distances in a spatial random graph version (Papers [1], [2], [3])
• Directed random graphs and PageRank (Chapter 9.2 and 1.6 in VOL 1)
• Preferential attachment (Chapter 8 in VOL 1 and Chapter 5, 2 talks)