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.

Literature

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)