High-dimensional random geometric graphs and their clique number

By Luc Devroye, András György, Gábor Lugosi, Frederic Udina. 2011

65 citations recorded by the source corpus.

We study the behavior of random geometric graphs in high dimensions. We show that as the dimension grows, the graph becomes similar to an Erdos-Renyi 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 Erdos-Renyi 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.

Subfields: Applied Mathematics, Mathematical Physics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/a2d8054ab7b23edd6cc5ff7260a674f709ab202a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

  1. Gábor Lugosi
  2. Sébastien Bubeck
  3. Radosław Adamczak

In Mathematical Physics

  1. Ery Arias-Castro
  2. Gábor Lugosi
  3. Sébastien Bubeck

In Signal Processing

  1. Ery Arias-Castro
  2. Gábor Lugosi
  3. Sébastien Bubeck
  4. John C. Duchi
  5. Michael I. Jordan
  6. Martin J. Wainwright

Citations in the corpus