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
P_{n}(λ) = e^{−λ}λ^{n}/n!, the Poisson distribution.
Summing from n=0 note that

ΣP_{n}(λ) = Σ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'

The way we picked this point made it n time as likely to pick a point with n links to it.

nP_{n}(λ)
= n e^{−λ}λ^{n}/n!
= e^{−λ}λ^{n}/(n−1)!
= λ e^{−λ}λ^{n−1}/(n−1)!
= λP_{n−1}(λ)

and P'_{0}(λ) = 0.

Let E

E

E

E

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

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.