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.