\problemdata      
        {?} % latex-friendly label for the prob.
        {Graphs, Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, final} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).



\begin{problem} 
A \emph{simple $k$-cycle} in a simple graph is an
undirected path going through each of $k>2$ vertices exactly once and
ending where it started.  A simple $k$-cycle can be represented by the
sequence of $k$ vertices $v_1, v_2, \ldots, v_k$ along the path.

Note that every $k$-cycle can be represented by many sequences.  For
example, the 4-cycle represented by $1234$ is as the same cycle represented
by $2341$ or $3412$ because a cycle does not have to start at any
particular vertex.  It is also represented by $4321$, because the cycle is
undirected.
\bparts

\ppart How many different sequences of vertices represent a given
$k$-cycle?\brule{0.7in}

\solution{$2k$}


\ppart How many $k$-cycles are there in a complete graph (all possible
edges are present) with $n$ vertices.\brule{0.7in}\\
\hint For $n=k=3$, the answer is 1.

\solution{$P(n,k)/2k$.

The number of ways of choosing a ordered sequence of $k$ vertices is
$P(n,k)$, but each $k$-cycle is represented by $2k$ such sequences.}

\eparts

Suppose we construct a simple $n$-node graph, $G=(V,E)$, randomly as follows:

For every set of two distinct vertices $\set{v,v'}$, toss a biased coin
whose probability of coming up heads is $p$.  The undirected edge between
$v$ and $v'$ is included in $E$ iff the coin comes up heads.  Assume that
all coin tosses are mutually independent.

\bparts

\ppart What is the probability that a $k$-cycle represented by a particular
sequence $v_1, v_2, \dots, v_k$ exists in $G$?

\solution{A particular $k$-cycle (call it $e$) will occur only if all of
the edges in that cycle exist in the randomly constructed $G=(V,E)$.  Since
each edge is independently added with probability $p$, we have $\pr{e \in
E} = p^k$.}

\ppart What is the expected number of $k$-cycles in $G$?  (Note: If
you were not able to solve part (b), you may let $X$ denote the answer
to part (b) and express your answer in terms of $X$, $k$, and $p$).

\solution{
Let $I_e$ be the indicator random variable of the event that a
particular $k$-cycle, $e$, occurs.  So the number, $N$, of $k$-cycles is
$\sum_e I_e$ where $e$ ranges over all possible $k$-cycles, \ie all
$k$-cycles in the complete graph on $V$.

We know from a previous part that $\pr{I_e = 1} = p^k$, which means that
$\expect{I_e} = p^k$.  Also, the total number of distinct possible
$k$-cycles is $X \eqdef P(n,k)/2k$.

Therefore
\[
\expect{N} = \sum_e \expect{I_e} = X p^k.
\]
}
                                                          
\eparts 
\end{problem} 
