Postdoc Seminar

Title: Simulating rare random graphs using importance sampling schemes based on large deviations

Abstract: We discuss some recent concentration of measure results and large deviations results for the Erdos-Renyi graph, and in particular its implications for the probability of rare graphs with large triangle counts. In the high temperature regime, two proofs of the large deviations result, one using a exponential random graph tilt and the other using an inhomogeneous graph tilt, provide different classes of tilted measures on which to build the importance sampling scheme. We analyse the asymptotic optimality of the two tilts and compare how they perform numerically. If time permits, we will briefly discuss the low temperature regime in which much less is known about the rare event of interest.
(Joint work with S. Bhamidi, J. Nolen, J. Hannig)