On the clique number of noisy random geometric graphs
Type:
Papers
Publisher:
Random Structures & Algorithms
Submitted:
Oct 2022
Accepted:
Oct 2022
Publication date:
2023
Abstract:
Let Gn be a random geometric graph, and then for \pp,\qqq∈[0,1) we construct a \emph{(\pp,\qqq)-perturbed noisy random geometric graph} G\pp,\qqqn where each existing edge in Gn is removed with probability \pp, while and each non-existent edge in Gn is inserted with probability \qqq. We give asymptotically tight bounds on the clique number ω(G\pp,\qqqn) for several regimes of parameter.

External link: