Clique sizes in a unit disk graph

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.

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.