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:

Note that this graph is NOT directed. We didn't study directed graphs in enough detail

in this course.

Self-loops are allowed, so the graph might not be simple, but multiple edges between

vertices are not allowed (so, if f(a) = b and f(b) = a, then there is still only one edge

between them).

Answer the following questions about this scenario. Write answers as expressions

in terms of n.

(a) What is the probability that f is injective (1-1)?

(b) What is the probability that Gf is a simple graph? (Hint: multiple edges can't happen, so all we care about are self-loops.)

(c) What is the probability that Gf has exactly n edges? (Hint: if f(a) = b and

f(b) = a, then that only creates one edge in Gf )

(d) What is the probability that Gf is a simple graph with exactly n edges?

(e) If n <= 4, what is the probability that Gf is a planar graph? Justify your answer

briefly.

(f) If 4 < n <= 8, what is the probability that Gf is a planar graph? Justify your answer

briefly.

(g) What is the probability that Gf is one big cycle that contains all of the vertices? An example of this is in the image below.

(h) We are guaranteed to be able to color the vertices of Gf using at most colors.

(Pick the smallest possible number that is guaranteed to work for every possible f. The answer may or may not depend on n.)