Processing math: 100%

On the clique number of noisy random geometric graphs

Type: 
Papers
Publisher: 

Random Structures & Algorithms

Accepted: 
Oct 2022
Publication date: 
2023
Co-author: 
Matthew Kahle
Minghao Tian
Yusu Wang
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.