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
nPn(λ) = n e−λλn/n! = e−λλn/(n−1)! = λ e−λλn−1/(n−1)! = λPn−1(λ)
and P'0(λ) = 0.
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.
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.