Departmental Colloquium
S. R. Srinivasa Varadhan
Courant Institute of Mathematical Sciences, NYU
Large Deviations of Random Graphs
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.
Friday October 22, 2010 at 3:00 PM in SEO 636