2009

Prof. Béla Bollobás

University of Cambridge and University to Memphis

in cooperation with the Department of Mathematics

Tuesday, March 31, 2009 at 16:30 pm

Projections, Entropy and Sumsets

    In this talk I shall review Shearer's entropy inequality and its recent strengthening due to Madiman and Tetali, together with the projection inequality I proved with Thomason about fifteen years ago that generalizes the classical  sixty-year-old Loomis--Whitney inequality. Furthermore, I shall present the common extensions of all these inequalities Paul Balister and I have proved very recently. We have used these results to strengthen some of the  inequalities concerning sums of sets of integers proved recently by Gyarmati, Matolcsi and Ruzsa.

Wednesday, April 1, 2009 at 14:00 pm

 Models of Large-scale Real-life Networks

 In the last fifty years or so, much research has been done on various models of random graphs in mathematics and physics. Among the families of models that have been investigated over the years, two stand out: the mean-field models, whose study was started by Erdos and Renyi 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 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.

Thurday, April 2, 2009 at 11:00 am

Convergent Sequences of Sparse Graphs

       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.

More information 04-8249294 or This e-mail address is being protected from spambots. You need JavaScript enabled to view it