A RANDOM GRAPH

The construction. A random (undirected) graph with n vertices is constructed in the following way: pairs of vertices are randomly 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? Yes. For example, if the vertex pair {x, y} were to be selected subsequently, there would now be more than one edge connecting x and y: a multiple edge or cycle 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 n = O(m).

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)}

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

p = \{ \begin{matrix}0 & if 0 < c ≤ 2 \\ e^{\frac{1}{c}} √1 − \frac{2}{c} & if c > 2 . \end{matrix}

“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, ….

Erdös and Renyi^{∗} show that the distribution of X_{k}^{(n)} is asymptotically Poisson: in particular,

lim_{n→∞} p_{k}^{(n)} = e^{−λ_{k}} ,

where

λ_{k} = (\frac{2}{c} )^{k} \frac{1}{2k} .

It follows that

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

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

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} .  (1)

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 (1) is divergent. Thus, we may deduce immediately that if c ≤ 2, lim_{n→∞} p^{(n)} exists and equals 0.

The interesting case c > 2 is also easily dealt with. When c > 2, we have that 0 < λ_{k} < 1 and that

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

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)} .

But, by Lemma 2 of [HM], we know have that, for each fixed k ≥ 2, EX_{k}^{(n)} ↑ λ_{k}, as n → ∞. In particular, for each fixed k ≥ 2, the sequence {EX_{k}^{(n)} } is bounded above by λ_{k}. It follows that {q_{k}^{(n)} } is bounded above by c_{k} := − log (1 − λ_{k}). Further, since λ_{k} < 1, we have

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

Thus, by the Lebesgue Dominated Convergence Theorem, we have that

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

and, hence, that lim_{n→∞} p^{(n)} exists and is equal to e^{−λ}.