Abstract

In the last fifty years or so, much research has been done on various models of random graphs in mathematics, computer science and physics. Among the families of models that mathematicians have worked on over the years, two stand out: the mean-field models, whose study was started by Erd˝os and R´enyi in the late 1950s, and the percolation models, based on lattices and lattice-like infinite graphs, introduced by Broadbent and Hammersley at about the same time. By now, we have elaborate and deep theories of random subgraphs of complete graphs and of percolation on lattices.

It was realized only fairly recently that random graph models may be very important in the study of massive graphs that occur in real life, like the graph of the World Wide Web, or various biological networks. These graphs are too big to describe precisely, and even if we could get all the information about them, this information could not be handled efficiently. It seems that the best we can do is model them as well as we can, and study the model. At the first sight it is surprising that the best models seem to be random graphs, although this is much less surprising if we realize that many of these graphs arise by a mixture of deterministic constructions and random decisions.

In the talk we shall review a number of these models, and present several results about them, including some I have obtained jointly with Oliver Riordan and Svante Janson.