A RANDOM GRAPH

The construction. A random (undirected) graph with n vertices is constructed in the following way: pairs of vertices are selected one at a time in such a way that each pair has the same probability of being selected on any given occasion, and, each selection is made independently of previous selections. If the vertex pair {x, y} is selected, then an edge is constructed which connects x and y.

Are multiple edges possible? In my model, yes! For example, if the vertex pair {x, y} were to be selected k times, there would be k edges connecting x and y: a multiple edge contributing \binom{k}{2} cycles of length 2.

ASYMPTOTIC BEHAVIOUR

Suppose that m edges have been selected. We shall be concerned with the behaviour of the graph in the limit as n and m become large, but in such a way that m = O(n).

The problem. Our problem is to determine the limiting probability that the graph is acyclic.

Motivation. Havas and Majewski^{∗} present an algorithm for minimal perfect hashing (used for memory-efficient storage and fast retrieval of items from static sets) based on this random graph. Their algorithm is optimal when the graph is acyclic.

∗[HM] Havas, G. and Majewski, B.S. (1992), Optimal algorithms for minimal perfect hashing, Technical Report No. 234, Key Centre for Software Technology, Department of Computer Science, The University of Queensland.

WHY ACYCLIC?

Consider a set W of m words (or keys). Every bijection h : W → I, where I = {0, …, m − 1}, is called a minimal perfect hash function. HM find hash functions of the form

h(w) = (g(f_{1}(w)) + g(f_{2}(w))) mod m;

f_{1}, f_{2} map keys to integers (they identify the pair of vertices of the graph corresponding to the edge w) and g maps integers to I.

Given f_{1} and f_{2}, can g be chosen so that h is a bijection?

If the graph is acyclic then, yes, it is easy to construct g from h. Traverse the graph: if vertex w is reached from vertex u then set

g(w) = (h(e) − g(u)) mod m ,

where e = (u, w).

EFFICIENCY

HM’s algorithm generates f_{1} and f_{2} at random until an acyclic graph is found:

f_{k}(w) = ( |w| ; ∑ ; i=1 T_{k}(i)w[i]) mod m ,

where T_{1} and T_{2} are tables of random integers and w[i] denotes the i-th character (an integer) of key i.

The efficiency of the algorithm is determined by the probability p^{(n)} that the graph is acyclic: the expected number of iterations needed to find an acyclic graph will be 1/p^{(n)} (typically between 2 and 3).

EVALUATING p^{(n)}

Theorem. If n and m tend to ∞ in such a way that m ∼ cn, where c is a positive constant, the limiting probability p that the graph is acyclic is given by

p = \{ \begin{matrix}e^{c}√1 − 2c & if 0 < c < 1/2 \\ 0 & if c ≥ 1/2 \end{matrix}

Proof. On request. It uses results from [HM] and Erdös and Renyi^{∗}.

∗[ER] Erdös, P. and Renyi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61.

SKETCH PROOF

Let X_{k}^{(n)} be the number of cycles of length k and let p_{k}^{(n)} = Pr(X_{k}^{(n)} = 0). Following [HM] write

p^{(n)} = ∞ ; ∏ ; k=2 p_{k}^{(n)} , n = 2, 3, ….

Now let q_{k}^{(n)} = − log p_{k}^{(n)} , so that 0 ≤ q_{k}^{(n)} < ∞ and

p^{(n)} = exp (− ∞ ; ∑ ; k=2 q_{k}^{(n)} ) , n = 2, 3, ….

ER show that the distribution of X_{k}^{(n)} is asymptotically Poisson: in particular,

lim_{n→∞} p_{k}^{(n)} = e^{−λ_{k}}, where λ_{k} = (2c)^{k}/2k.

It follows that

lim_{n→∞} q_{k}^{(n)} = − log ( lim_{n→∞} p_{k}^{(n)} ) = λ_{k} .

So, formally,

lim_{n→∞} ∞ ; ∑ ; k=2 q_{k}^{(n)} = ∞ ; ∑ ; k=2 lim_{n→∞} q_{k}^{(n)} = ∞ ; ∑ ; k=2 λ_{k} ,

and hence

lim_{n→∞} p^{(n)} = e^{−λ} , where λ = ∞ ; ∑ ; k=2 λ_{k} .  (2)

By Fatou’s Lemma, we always have

lim inf_{n→∞} ∞ ; ∑ ; k=2 q_{k}^{(n)} ≥ ∞ ; ∑ ; k=2 lim inf_{n→∞} q_{k}^{(n)} = ∞ ; ∑ ; k=2 λ_{k} ,

from which it follows immediately that

lim sup_{n→∞} p^{(n)} ≤ e^{−λ};

this argument is valid even if the sum in (2) is divergent. We deduce immediately that if c ≥ 1/2, p^{(n)} → 0.

When c < 1/2, we have 0 < λ_{k} < 1 and

λ = ∞ ; ∑ ; k=2 λ_{k} = −c + \frac{1}{2} ln (\frac{1}{1 − 2c} ) .

From Markov’s inequality we have Pr(X_{k}^{(n)} ≥ 1) ≤ EX_{k}^{(n)} and so p_{k}^{(n)} = Pr(X_{k}^{(n)} = 0) ≥ 1 − EX_{k}^{(n)} . By Lemma 2 of [HM], we have, for each fixed k ≥ 2, that EX_{k}^{(n)} ↑ λ_{k} as n → ∞. In particular, for each k ≥ 2, the sequence {EX_{k}^{(n)} } is bounded above by λ_{k}. It follows that {q_{k}^{(n)} } is bounded above by d_{k} := − log (1 − λ_{k}). Further, since λ_{k} < 1,

∞ ; ∑ ; k=2 d_{k} = − log ( ∞ ; ∏ ; k=2 (1 − λ_{k}) ) < ∞ .

Thus, by Dominated Convergence, we have

lim_{n→∞} ∞ ; ∑ ; k=2 q_{k}^{(n)} = ∞ ; ∑ ; k=2 lim_{n→∞} q_{k}^{(n)} = λ ,

and, hence, p^{(n)} → e^{−λ}.

THE FIVE STAGES OF EVOLUTION PRIMORDIAL STEW: m(n) = o(n)

If m(n)/n → 0, then (with limiting probability 1) all components are trees.

Trees of order k appear when m reaches order n^{(k−2)/(k−1)} . In particular, T_{k}, the number of trees of order k, has a (limiting) Poisson distribution with mean λ_{k} = (2ρ)^{k−1}k^{k−2}/k!, where

ρ = lim_{n→∞} m(n)n^{(k−1)/(k−2)} .

Finally, if m(n)n^{(k−1)/(k−2)} → ∞, the number of trees of order k is asymptotically normally distributed with mean and variance equal to

μ_{n} = n\frac{k^{k−2}}{k!} (\frac{2m(n)}{n} )^{k−1} e^{−2km(n)/n} .

To be precise, (T_{k} − μ_{n})/√μ_{n} ⇒ N(0, 1). This result holds in the next two stages of evolution; we only require μ_{n} → ∞.

SPOOKY: m(n) ∼ cn, where

0 < c < 1/2

Cycles of all orders start to appear: C_{k}, the number of cycles of order k, has a (limiting) Poisson distribution with mean λ_{k} = (2c)^{k}/(2k).

Furthermore, with limiting probability 1, all components are either trees or consist of exactly one cycle (k vertices and k edges), the latter having a Poisson distribution with mean

λ_{k} = \frac{(2ce^{−2c})^{k}}{k!} k−3 ; ∑ ; i=0 \frac{k^{i}}{i!} ,

where k is the order of the cycle.

The largest component is a tree; it has

\frac{1}{2c − 1 − log 2c} (log n − \frac{5}{2} log log n)

vertices (with probability tending to 1).

A MONSTER APPEARS:

m(n) ∼ cn, where c ≥ 1/2

When m(n) ∼ n (c = 1/2), the largest component has (with probability tending to 1) n^{2/3} vertices. When m(n) ∼ cn with c > 1/2, a giant component appears: the largest component in the graph has G(c)n vertices, where G(c) = 1 − X(c)/2c and

X(c) = ∞ ; ∑ ; i=1 \frac{i^{i−1}}{i!}(2ce^{−2c})^{i} .

Note that G(1/2) = 0 and G(c) → 1 as c → ∞.

Almost all the other vertices belong to trees: the total number of vertices belonging to trees is almost surely n(1 − G(c)) + o(n).

For c > 1/2, the expected number of components in the graph is asymptotically

\frac{n}{2c} (X(c) − \frac{1}{2}X^{2}(c)) .

CONNECTEDNESS:

m(n) ∼ cn log n, where 0 < c ≤ 1/2

The graph is becoming connected: if

m(n) = \frac{n}{2k} log n + \frac{k − 1}{2k}n log log n + αn + o(n),

then (with probability tending to 1) there are only trees of order ≤ k outside the giant component, the limiting distribution of the number of trees of order l being Poisson with mean e^{−2αl}/(l.l!). For example (k = 1), if

m(n) = \frac{n}{2} log n + αn + o(n),

there are (almost surely) only isolated vertices outside the giant component, the number of these having a limiting Poisson distribution with mean e^{−2α}. And, the chance that the graph is indeed connected tends to exp (−e^{−2α}) (which itself tends to 1 as α grows).

ASYMPTOTIC REGULARITY:

m(n) ∼ ω(n)n log n, where ω(n) → ∞

The whole graph becomes regular: with probability tending to 1, the graph becomes connected and the orders of all vertices are equal.