Computer Science/Discrete Mathematics Seminar I

Recently, Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi introduced a natural metric on the space of dense graphs, and identified the completion of the metric space that arises. Independently and simultaneously, Janson, Riordan and I defined a very general model of sparse inhomogeneous random graphs which include many of the models of real-world graphs that have been studied in the past decade. The functions used to define these models are very similar to the points of the completion of the space of dense graphs. In this talk I shall describe some rather tentative attempts that Riordan and I have made to bring about a general theory of metrics on sparse graphs. The difficulties that arise are considerably greater than in the dense case, so that at the moment there are more conjectures and open problems than results.