. Let S be a set containing n elements. You pick a random function f : S S by

choosing what each element maps to independently, with equal probability assigned to

every possible output.

For example, if S = {a,b}, then:

P(f(a) = a) = P(f(a) = b) = P(f(b) = a) = P(f(b) = b) = 1/2

Now, for our function f, we define the graph Gf in the following way: Gf = (S,E), such

that there is an edge between vertices x and y iff f(x) = y. For example, if S = A,B,C

and f is such that f(A) = B, f(b) = C, and f(C) = C, then we get a graph like this:

\f\f