SPEAKER: Vijaya Ramachandran
TIME: Thursday 4:30-5:30 pm, October 19th, 2006
PLACE: PPB 300
TITLE: The Diameter of Sparse Random Graphs
ABSTRACT:
We derive an expression of the form $c ln n + o(ln n)$ for the diameter of a sparse random graph with a specified degree sequence. The result holds a.a.s., assuming certain convergence and supercriticality conditions are met. The classes of random graphs for which this result applies include the classical random graph model $G_{n,p}$ when $p=(1+b)/n$ for any positive constant $b$, and ‘power-law’ graphs when the giant component exists and the number of edges is linear in the number of vertices. The proof is constructive and yields a method for computing the constant $c$. Our methods also establish that almost all pairs of vertices that are connected by a path in such a random graph have almost the same shortest path distance.
This is joint work with Dan Fernholz.
