High-Dimensional Random Geometric Graphs and their Clique Number

著者: Luc Devroye, András György, Gábor Lugosi, Frederic Udina - Electronic Journal of Probability 2011 被引用: 62

We study the behavior of random geometric graphs in high dimensions. We show that as the dimension grows, the graph becomes similar to an Erds-Rnyi random graph. We pay particular attention to the clique number of such graphs and show that it is very close to that of the corresponding Erds-Rnyi graph when the dimension is larger than log 3 n where n is the number of vertices. The problem is motivated by a statistical problem of testing dependencies..