Topology in Molecular Biology

12 The Spectral Geometry of Riemann Surfaces 231

Theorem 10.The cycle decomposition of a randomly picked element ofS(n)
has the following properties:

1. The expected number of cycles is∼log(n).


2. There is a constantcsuch that the expected length of the longest cycle is
   at leastc·n.

I do not know to whom to attribute these results, but they have been actively
studied and generalized in recent years. The precise value ofchas been com-
puted, and is something like. 62 ..., but we will present a simple argument
showing thatc≥ 1 /2. The reason for doing this is that the simple argument
will generalize to the setting of three-regular graphs, once we clarify what the
right translation to this setting is. As a result, the constant 1/πappearing in
Theorem 7.2 is certainly not sharp, and our belief is that it should probably
be about twice as big, but already the simple estimate gives us a striking
geometric fact.
We would like to leave the correct estimate of the constant on the hands
of experts.
Theorem 7.3 can be seen easily from what has become known asthe
spaghetti model. Imaginenpieces of spaghetti, labeled from 1 ton, lined
up so that each piece lies vertically. At each step of the process, one ties the
bottom of one piece of spaghetti, chosen randomly, to the top of another piece
of spaghetti, again chosen randomly. In this way, one creates an element of
the symmetric group, and the number of components of spaghetti and their
corresponding lengths correspond to the number of cycles and their respective
lengths.
At thekth step of the process, the probability of forming a closed loop is
exactly 1/(n−k+ 1), as is easily seen. Thus the expected number of closed
loops at the end will be

1 /n+1/(n−1) +···+1∼log(n).

Now let us modify the process in the following way: at the first step, the
bottom piece of spaghetti is chosen to be the first one. At thekth step, we pick
as the bottom piece the piece whose top piece was chosen at the (k−1)th step.
We continue in this way until a closed loop is formed. What is the expected
length of this loop?
Well, the probability of its length 1 is 1/n. The probability of its length 2
is
[(n−1)/n][1/(n−1)] = (n+1)/ 2 ∼n/ 2.

In general, it is not hard to see that the probability of the process stopping
at exactlyksteps is exactly 1/n. So the expected value is easily computed to
be
(1/n)[1 +···+n]=(n+1)/ 2 ∼n/ 2.
We remark that one could do a similar computation where one modifies
the process by picking at random a free end, disregarding whether it is a top