F. Udina Abelló, L. Devroye, A. György, G. Lugosi
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-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 corre- sponding Erdo ̋s-Rényi graph when the dimension is larger than log3 n where n is the number of vertices. The problem is motivated by a statistical problem of testing dependencies.
Palabras clave: clique number, dependency testing, geometric graphs, random graphs
Programado
VB7 Probabilidad, convergencias y teoremas límite
20 de abril de 2012 10:30
Sala Roma II
