Random Graphs

by Svante Janson (Uppsala University)

Wednesday 29 Jan 2014, 14:15 → 16:15 Europe/Stockholm

Lecture hall Oskar Klein

Random graphs are graphs generated by some random procedure. The main interest is in asymptotics for very large graphs. The theory was started by a series of papers by Erdös and Renyi, beginning in 1959, where they studied many aspects of the random graph model G(n,m) with a fixed number of vertices n and a fixed number of edges m, all possibilities having the same probability. This model and the closely related model G(n,p) where edges appear independently have since then been the standard models. I will discuss some typical problems and results, including existence of small subgraphs, connectivity, and existence of a giant component.

A typical feature is that many properties show a threshold phenomenon: random graphs with few edges (m or p above small in relation to n) will not have the property (except with a small probability), but as the number of edges grows, there is a rather sudden transition to a case where the property holds (except with a small probability).

In later years, this model has been complemented by many other random graph models. I will mention some of the more important, in particular the "configuration model" (Bollobas and others) and "preferential attachment" (Barabasi-Albert and others).

Short-CV Svante Janson grew up in Dalarna, Sweden. He left school at the age of 11 and began taking university courses in mathematics. He formally became a university student at the age of 12, and received his bachelor in mathematics at Uppsala University at the age of 14. He defended his PhD thesis (supervised by Lennart Carleson) on his 22nd birthday (1977). He received a second PhD, this time in mathematical statistics, at the age of 28 (1984) and became professor in mathematics at Uppsala University 1987. He is member of the Swedish Academy of Sciences. Beside shorter post doc and similar research visits and one year at Stockholm University as docent, he has been at Uppsala University all the time.

Svante Janson's research covers several areas of mathematics: mathematical analysis, probability, combinatorics and random algorithms, and in particular random graphs, the topic of the colloqium. Svante Janson has (by January 10, 2014 at 10.03) published 4 monographs and 288 papers with 152 collaborators.