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?

L is a symmetric relation and xLy iff x is linked to y. If I is the identity relation then the transitive closure of L∪I is an equivalence relation that defines the cliques as equivalence sets.

A clique is a set of points between any two of which there is a sequence of points with successive members 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)!
The way we picked this point made it n time as likely to pick a point with n links to it.

nPn(λ) = n e–λλn/n! = e–λλn/(n–1)! = λ e–λλn–1/(n–1)! = λPn–1(λ)

and P'0(λ) = 0.

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–λ).

Application

About 1957 there were many different digital media. One numerical machine tool was driven by 19 track punched metallic tape. For such a machine there was provided by the manufacturer some device, perhaps manual, to prepare information on the medium. Livermore was ahead of the curve in the new art of computerized production of such information. Livermore had many such media to contend with. Someone kept a list of devices available at Livermore for transcoding information from one medium to another. I recall some point when the shortest path between two particular media was 19 steps.

Digital Equipment’s PDP-1 was a computer that had been designed to make interfacing of digital equipment particularly easy. Shortly after its arrival Livermore engineers adapted the specialized media drivers to the PDP-1 which thereby became a media hub.