High-dimensional random geometric graphs and their clique number

被引：36

作者：

Devroye, Luc ^{[1
]}

Gyoergy, Andras ^{[2
]}

Lugosi, Gabor ^{[3
]}

Udina, Frederic ^{[3
]}

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ H3A 2A7, Canada

[2] Hungarian Acad Sci, Machine Learning Res Grp, Comp & Automat Res Inst, H-1111 Budapest, Hungary

[3] Pompeu Fabra Univ, Dept Econ, Barcelona 08005, Spain

来源：

ELECTRONIC JOURNAL OF PROBABILITY | 2011年 / 16卷

关键词：

Clique number; dependency testing; geometric graphs; random graphs;

D O I：

10.1214/EJP.v16-967

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

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..

引用

页码：2481 / 2508

页数：28

共 19 条

[1]

Alon N, 1998, RANDOM STRUCT ALGOR, V13, P457, DOI 10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO

[2]

2-W

[3]

Alon Noga, 1992, The Probabilistic Method

[4]

Ane C., 2000, INEGALITES SOBOLEV L

[5]

[Anonymous], 1985, Graphical Evolution

[6]

[Anonymous], 2003, OXFORD STUDIES PROBA

[7]

[Anonymous], LECT NOTES MATH

[8]

[Anonymous], 1998, Random graphs

[9] On the dependence of the Berry-Esseen bound on dimension [J].

Bentkus, V .

JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 2003, 113 (02) :385-402

[10] Deterministic and randomized polynomial-time approximation of radii [J].

Brieden, A ;

Gritzmann, P ;

Kannan, R ;

Klee, V ;

Lovász, L ;

Simonovits, M .

MATHEMATIKA, 2001, 48 (95-96) :63-105

← 1 2 →