# Student Probability Seminar

#### Localization in Random Geometric Graphs with Too Many Edges

Speaker: Matan Harel

Location: Warren Weaver Hall 1314

Date: Thursday, February 28, 2013, 3:30 p.m.

Synopsis:

Consider a random geometric graph $$G(n, r)$$, given by taking a Poisson Point Process of intensity $$n$$ on the $$d$$-dimensional unit torus and connecting any two points whose distance is smaller than $$r$$. We condition this model on the rare event that the observed number of edges $$|E|$$ exceeds its expected value $$\mu$$ by a multiplicative constant larger than one - i.e. greater than $$(1 + \delta) \mu$$, for some fixed positive $$\delta$$. We prove that, with high probability, this implies the existence of a ball of diameter $$r$$ with approximately $$\sqrt{2 \delta \mu}$$ vertices, making up a clique with all the "extra" edges in the graph.