High-Dimensional Random Geometric Graphs and their Clique Number

Luc Devroye (McGill University)
András György (Hungarian Academy of Sciences)
Gábor Lugosi (Pompeu Fabra University)
Frederic Udina (Pompeu Fabra University)

Abstract


We study the behavior of random geometric graphs in high dimensions. We show that as the dimension grows, the graph becomes similar to an Erdös-Rényi 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 Erdös-Rényi 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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 2481-2508

Publication Date: November 30, 2011

DOI: 10.1214/EJP.v16-967

References

  1. Alon, Noga; Krivelevich, Michael; Sudakov, Benny. Finding a large hidden clique in a random graph. Proceedings of the Eighth International Conference "Random Structures and Algorithms'' (Poznan, 1997). Random Structures Algorithms 13 (1998), no. 3-4, 457--466. MR1662795 (99k:05144)

  2. Alon, Noga; Spencer, Joel H. The probabilistic method. With an appendix by Paul Erdős. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. xvi+254 pp. ISBN: 0-471-53588-5 MR1140703 (93h:60002)

  3. Ané, Cécile; Blachère, Sébastien; Chafaï, Djalil; Fougères, Pierre; Gentil, Ivan; Malrieu, Florent; Roberto, Cyril; Scheffer, Grégory. Sur les inégalités de Sobolev logarithmiques. (French) [Logarithmic Sobolev inequalities] With a preface by Dominique Bakry and Michel Ledoux. Panoramas et Synthèses [Panoramas and Syntheses], 10. Société Mathématique de France, Paris, 2000. xvi+217 pp. ISBN: 2-85629-105-8 MR1845806 (2002g:46132)

  4. Bentkus, V. On the dependence of the Berry-Esseen bound on dimension. J. Statist. Plann. Inference 113 (2003), no. 2, 385--402. MR1965117 (2004b:60061)

  5. Bollobás, Béla. Random graphs. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. xvi+447 pp. ISBN: 0-12-111755-3; 0-12-111756-1 MR0809996 (87f:05152)

  6. Brieden, Andreas; Gritzmann, Peter; Kannan, Ravindran; Klee, Victor; Lovász, László; Simonovits, Miklós. Deterministic and randomized polynomial-time approximation of radii. Mathematika 48 (2001), no. 1-2, 63--105 (2003). MR1996363 (2004f:52012)

  7. Chernoff, Herman. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics 23, (1952). 493--507. MR0057518 (15,241c)

  8. Danzer, Ludwig; Grünbaum, Branko; Klee, Victor. Helly's theorem and its relatives. 1963 Proc. Sympos. Pure Math., Vol. VII pp. 101--180 Amer. Math. Soc., Providence, R.I. MR0157289 (28 #524)

  9. Dudley, R. M. Central limit theorems for empirical measures. Ann. Probab. 6 no. 6, 899--929 (1979). MR0512411 (81k:60029a)

  10. Erdős, P.; Rényi, A. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 1960 17--61. MR0125031 (23 #A2338)

  11. Janson, Svante; Łuczak, Tomasz; Rucinski, Andrzej. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. xii+333 pp. ISBN: 0-471-17541-2 MR1782847 (2001k:05180)

  12. Jung, H. Über die kleinste Kugel, die eine räumliche Figur einschliesst. J. Reine Angew. Math. 123 1901 241--257.

  13. Massart, Pascal. Concentration inequalities and model selection. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23, 2003. With a foreword by Jean Picard. Lecture Notes in Mathematics, 1896. Springer, Berlin, 2007. xiv+337 pp. ISBN: 978-3-540-48497-4; 3-540-48497-3 MR2319879 (2010a:62008)

  14. Nadakudit, R.R.; Silverstein, J.W. Fundamental limit of sample generalized eigenvalue based detection of signals in noise using relatively few signal-bearing and noise-only samples Technical Report. 2009.

  15. Palmer, Edgar M. Graphical evolution. An introduction to the theory of random graphs. Wiley-Interscience Series in Discrete Mathematics. A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester, 1985. xvii+177 pp. ISBN: 0-471-81577-2 MR0795795 (87a:05121)

  16. Penrose, Mathew. Random geometric graphs. Oxford Studies in Probability, 5. Oxford University Press, Oxford, 2003. xiv+330 pp. ISBN: 0-19-850626-0 MR1986198 (2005j:60003)

  17. Raič, M.. Normalna aproksimacija po Steinovi metodi. PhD thesis, Univerza v Ljubljani, 2009.

  18. Vapnik, V. N.; Chervonenkis, A. Ya. \cyr Teoriya raspoznavaniya obrazov. Statisticheskie problemy obucheniya. (Russian) [Theory of pattern recognition. Statistical problems of learning] Izdat. ``Nauka'' WHERE article_id=Moscow, 1974. 415 pp. MR0474638 (57 #14274)

Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.