S. R. Srinivasa Varadhan : Large Deviations of Random Graphs

Posted by Emily Dumas , part of the Departmental Colloquium.

At

Oct. 22, 2010, 3 p.m.

In

SEO 636

Abstract

In this joint work with Sourav Chatterjee, we consider a random graph with $n$ vertices, with probability $p$ for any given edge to be present. We consider the case when $p$ is fixed and $n$ gets large. Asymptotically the expected number of edges is $~{1\over 2}n^2$ and the expected number of triangles is $~{1\over 6}n^3$. We look at the large deviation probabilities for these numbers as well as other subgraph counts. This allows us to say, for example, what a graph with more than the normal number of triangles will look like. The model exhibits an interesting phase transition.