Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a spiritual successor to a question that Peter Shor answered here:

Generalized Euclidean TSP

Are there any results known on the asymptotic behavior of clique sizes in a unit disk graph with uniformly sampled points? That is, suppose I sample $N$ points uniformly in a square (or disk, or whatever figure is easiest to deal with) of size $L \times L$, and I draw an edge between two points if the distance between them is less than $1$. As $N$ becomes large, is anything known about the distribution of clique sizes in this graph?

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

Yes, a lot is known about this. See Mathew Penrose's book, "Random Geometric Graphs." He discusses subgraph counts for random geometric graphs on distributions with bounded, measurable, density functions --- this includes uniform distributions on any convex body as a special case. He also discusses maximum clique size.

See also his recent paper with Yukich, Limit theory for point processes in manifolds.

share|improve this answer
add comment

Hi Gunnar,

The behaviour of the clique number = max.clique size will depend on L (you may want to keep L fixed, or let it grow with $N$ in some way). Dropping $N$ points in a $L\times L$ box and connecting when the distance is less than 1 is the same as dropping $N$ points in the unit square and connecting is the distance is less than $r = 1/L$.

The book by Penrose and an earlier paper by McDiarmid (random channel assignment in the plane", Random Structures & Algorithms, Volume 22, Issue 2, pages 187–212) describe the "first order" behaviour of the clique number. Basically there are three case depending on whether the "average degree" $N \pi r^2$ is $\ll \log N$, $\Theta( \log N )$ or $\gg \log N$. In each case there is an expression $f(N,r)$ such that clique.no divided by $f(N,r)$ tends to one in probability. This of course does not answer all questions about the clique number. One may for instance wonder whether the clique number can somehow be normalized to tend to some known limiting distribution.

(This is not very chique, I know, but) you may also want to have a look at a paper by me (tobias mueller) "Two point concentration in random geometric graphs", Combinatorica, Volume 28, Number 5, 529-545.

It solves a conjecture on the probability distribution of the max.clique size posed by Penrose in his book. Namely that the probability mass of the max.clique size becomes concentrated on two consecutive integers when the parameters are chosen such that $N \pi r^2 \ll \log N$. I.e. if $N, r$ satisfy this condition then there is a function $k(N,r)$ such that

${\mathbb P}( k \leq \text{clique.no} \leq k+1 ) \to 1$,

as $N\to\infty$.

For other choices of the parameters, if $N\pi r^2 = \Theta( \log N )$ or $\gg \log N$, the (asymptotic) probability distribution of the clique number is an open problem -- see the conclusion of that paper.

share|improve this answer
    
Thanks, Tobias! –  John Gunnar Carlsson Jan 1 '12 at 21:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.