Percolation on sequences of graphs

Conference item

Recently many new random graph models have been introduced, motivated originally by attempts to model disordered large-scale networks in the real world, but now also by the desire to understand mathematically the space of (sequences of) graphs. This article will focus on two topics. Firstly, we discuss the percolation phase transition in these new models, and in general sequences of dense graphs. Secondly, we consider the question 'when are two graphs close?' This is important for deciding whether a graph model fits some real-world example, as well as for exploring what models are possible. Here the situation is well understood for dense graphs, but wide open for sparse graphs. The material discussed here is from a variety of sources, primarily work of Bollobás, Janson and Riordan and of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi. The viewpoint taken here is based on recent papers of Bollobás and the author.

Authors: Riordan, O

• Host title: Proceedings of the International Congress of Mathematicians 2010, ICM 2010
• Pages: 2555-2578
• Publication date: 2010-01-01
• ISBN-10: 9814324302
• ISBN-13: 9789814324304
• Keywords: Inhomogeneous random graphs; Phase transition; Metrics on graphs