Two-point concentration in random geometric graphs

Tobias Muller
Oxford University


Résumé:

A random geometric graph $G_n$ is constructed by taking vertices $X_1, ..., X_n \in R^d$ at random (i.i.d.~according to some probability distribution nu$$\) and including an edge between $X_i$ and $X-j$ if $|X_i-X_j| < r$ where $r=r(n) > 0$. We prove a conjecture of Penrose stating that when $n r^d = o(\ln n)$ then the probability distribution of the clique number $\omega(G_n)$ becomes concentrated on two consecutive integers in the sense that ${\mathbb P}(\omega(G_n) ∈ \{k(n), k(n)+1\} )$ tends to 1 for some sequence $k(n)$. We also show that the same holds for a number of other graph parameters including the chromatic number $\chi(G_n)$. A series of celebrated results establish that a similar phenomenon occurs in the Erd\H{o}s-R\'enyi or $G(n,p)$-model of random graphs.

Retour au séminaire