Department of Mathematics

Indian Institute of Science

Bangalore 560 012

 

SEMINAR

 

Speaker

:

Shankar Bhamidi, 
Affiliation : University of North Carolina, Chapel Hill

Subject Area

:

Mathematics

 

Venue

:

Lecture Hall I, Depatment of Mathematics, IISc.

 

Time

:

3:30 p.m.

 

Date  

:

Dec 31, 2009 (Thursday)

Title

:

Two philosophies for random graphs and networks: Local weak convergence and scaling limits
Abstract

:

  The last few years have witnessed an explosion in the number of mathematical models for random graphs and networks, as well as models for dynamics on these network 
  models. In this context I would like to exhibit the power of two well known philosophies in attacking problems in random graphs and networks:

Local weak convergence: The idea of local neighborhood of probabilistic discrete structures (such as random graphs) converging to the local neighborhood of limiting infinite objects has been known for a long time in the probability community and has proved to be remarkably effective in proving convergence results in many different situations.

Here we shall give a wide range of examples of the above methodology. In particular

[a] We shall show how the above methodology can be used to tackle problems of flows through random networks, where we have a random network with nodes communicating via least cost paths to other nodes. We shall show in some models on the completely connected network how the above methodology allows us to prove the convergence of the empirical distribution of edge flows, exhibiting how macroscopic order emerges from microscopic rules.

[b] We shall show how for a wide variety of random trees (uniform random trees, preferential attachment trees arising from a wide variety of attachment schemes, models of trees from Statistical Physics etc) the above methodology shows the convergence of the spectral distribution of the adjacency matrix of theses trees to a limiting non random distribution function.

Scaling limits: For the analysis of critical random graphs, one often finds that properly associated walks corresponding to the exploration of the graph encode a wide array of information (including the size of the maximal components). In this context we shall extend work of Aldous on Erd\H{o}s Renyi critical random graphs to the context of inhomogeneous random graph models. If time permits we shall describe the connection between these models and the multiplicative coalescent, arising from models of coagulation in the physical sciences.