There is a network puzzle being noised about that goes as follows.

Given an infinite number of points and some density λ of links between them for what value of λ do infinite size cliques appear. (A link connects two points and the expected number of links to a point is λ.) Perhaps an equivalent question is for what value of λ does the expected value of the size of a clique of a random point become infinite? Indeed are these well posed questions?

A clique is a set of points between any two of which there is a sequence of points pairwise connected by links.

The probability that a randomly selected point has n links to it is Pn(λ) = e–λλn/n!, the Poisson distribution. Summing from n=0 note that
ΣPn(λ) = Σe–λλn/n! = e–λΣλn/n! = e–λeλ = 1

If we select a random link and select one of its ends X, at random, then the distribution P' of the number of links to X is


P'n(λ) = nPn(λ) = n e–λλn/n! = e–λλn/(n–1)!
nPn(λ) = λPn–1(λ)
and P0(λ) = 0. This stems from the fact that we are likely to select X in proportion to the number of links to it.

Let En(λ) be the expected number of points that are just n links away from a randomly selected point X.
E0(λ) = 1
E1(λ) = λ
En(λ) = λn

It goes critical at λ = 1 which I find suprisingly small.

Now what is the distribution of the sizes of the finite cliques, and what fraction of the points belong to infinite cliques? 1/e of the points are not connected at λ = 1. If we select a random point the probability of just one link to it is 1/e and the probability of the other point having just that one link is 1/e thus the probability of a random point belonging to a twosome is just e–2.

Our random point may belong to a threesome in two ways, in the middle or at the end. As above the probability that it is at the end is e–3. This uses the fact that the probability of a point, selected randomly among those having at least one link, having just two is again 1/e. The probability of our random point being in the middle is (0.5/e)e–2 = e–3/2. It is comforting to see that it is twice as likely to be at the end as in the middle. These two ways of being in a threesome total to 0.75e–3. This calculation is getting ugly fast.


Another argument leads to some of the same results. Let x be the expected number of points accessible (linked directly or indirectly) thru just one end of a randomly selected link. x = 1+λx. In this equation the 1 counts the point at the end of the selected link and there are λ further links expected at that point each of which expect x accessible points. Solving for x we get x = 1/(1–λ). This also says that the expected size of the clique to which a randomly selected point belongs is 1+λ/(1–λ) = 1/(1–λ).