KTH/SU
Mathematics
Colloquium
October
19, 2005
Prof.
Svante Janson,
UU
RANDOM
GRAPHS
ABSTRACT: The
simplest type of random graphs is obtained by
taking a (large) set of vertices and then adding
edges at random such that each pair of vertices
is joined with some probability p, independently
of all other edges. A different but related
random graph is obtained by fixing the number of
edges and then placing them at random, uniformly
over all possible positions. The study of such
random graphs was initiated by Erdös and Renyi in
1960. I will describe some classical and some
rather new results on the structure of such
random graphs. A main result is the existence of
a giant component, with a large part of all
vertices, when the number of edges is
sufficiently large. I will also say something
about other, less homogeneous, types of random
graphs that have been studied recently, partly
motivated by a desire to model the structure of
the Internet by random graphs.