SoSe 21: Random Graphs
Michael Anastos
Additional information / Pre-requisites
This course can be taken as the third element of the Discrete Mathematics Master sequence. Successful completion of the course Discrete Mathematics I (or equivalent; contact the instructors for consent) is required, and completion of a Discrete Mathematics II course is highly beneficial. Basic knowledge of combinatorics and graph theory, probability, linear algebra and calculus is required.
closeComments
Random Graph Theory studies graphs (networks) that are chosen randomly from a large family G of graphs according to some distribution. One is interested in answering questions about what properties a random member of G is likely to have or whether there exists a member of G with the given property. The study of random graphs is a fascinating subject which initially developed in parallel within both combinatorics and statistical physics. In combinatorics it was primarily used to prove the existence of graphs with unexpected properties, where determinsitic approaches for a construction failed. Nowdays it is often applied to model and study large networks such as the internet, social networks, the spread of information etc In this course we start by reviewing the evolution of binomial random graphs and go on to study their basic graph theoretic properties including connectivity, small subgraph containment, independence / chromatic number and Ramsey properties. We will also treat various other random graph models including random graphs with a given degree sequence, random geometric graphs, preferential attachment graphs and weighted graphs.
closeSuggested reading
Main text:
- A Frieze, M Karonski, Introduction to random graphs (Cambridge University Press, 2016)
Further reading:
- B. Bollobas, Random Graphs, (Second Edition, Cambridge University Press, 2001)
- S. Janson, T. Luczak and A. Rucinski, Random Graphs, (Wiley, 2000)
- N. Alon, J. Spencer: The Probabilistic Method (Fourth edition, Wiley, 2016)
14 Class schedule
Regular appointments