On the clique number of noisy random geometric graphs

Abstract

Let $G_n$ be a random geometric graph, and then for $q,p\in [0,1)$ we construct a "$(q,p)$-perturbed noisy random geometric graph" $G_n^{q,p}$ where each existing edge in $G_n$ is removed with probability $q$, while and each non-existent edge in $G_n$ is inserted with probability $p$. We give asymptotically tight bounds on the clique number $\omega \left(G_n^{q,p}\right)$ for several regimes of parameter.

34 pages, 4 figures