2
$\begingroup$

I want to show that $\mu_{n}(p)$, the expected number of Hamiltonian cycles in the random graph $G(n,p)$, is given by

$$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$$

We can easily show that the number of the Hamiltonian cycles in a complete graph $K_{n}$ is given by $\frac{1}{2}(n-1)!$. Now, we let $X$ be a random variable counting the number of Hamiltonian cycles. Then the expectations of $X$ in a random graph $G(n,p)$ is $$E[X]= \displaystyle\sum_{i=1}^{k} x_ip_i$$ where $x_i$ denotes a Hamiltonian cycle in a complete graph $K_n$ and $p_i=p^n$ for all $i$, since each Hamiltonian cycle that occurs in $K_n$ occurs in $G(n,p)$ with probability $p^n$. Thus, using the linearity of the expectation, we get

$$E[X]= p^n\displaystyle\sum_{i=1}^{k} x_i=p^n\frac{1}{2}(n-1)!$$ as required. Does that make sense?

$\endgroup$
  • 1
    $\begingroup$ Yes, that is correct. FYI, calculations like this of the heart of the probabilistic method. $\endgroup$ – ericf Mar 19 at 5:45
  • $\begingroup$ Great, thank you. $\endgroup$ – amator2357 Mar 19 at 8:56
2
$\begingroup$

You are doing the calculation correctly, but I take some issue with your formalism. Specifically, you say that "$x_i$ denotes a Hamiltonian cycle in a complete graph $K_n$" but it's unclear what sort of object $x_i$ is, and why you replace every $x_i$ by $1$ in the final step.

So let me give you the conventional careful way of writing up the same calculation you do. (As you become used to this kind of argument, you will skip directly to multiplying $\frac12(n-1)!$ by $p^n$, but it's important to be able to fill in the intervening steps when you need to.)

Arbitrarily order the $k = \frac12(n-1)!$ Hamiltonian cycles in $K_n$ so that we can talk about the first cycle, second cycle, $i^{\text{th}}$ cycle, and so on. Define the random variable $$ X_i = \begin{cases}1 & \text{the $i^{\text{th}}$ cycle is present in $G(n,p)$,} \\ 0 & \text{otherwise.} \end{cases} $$ Then we have $$ X = X_1 + X_2 + \dots + X_k $$ and therefore by linearity of expectation $$ \mathbb E[X] = \mathbb E[X_1] + \mathbb E[X_2] + \dots + \mathbb E[X_k]. $$ Since each cycle is present with probability $p^n$, we have $\mathbb E[X_i] = p^n \cdot 1 + (1-p^n) \cdot 0 = p^n$ for each $i$, and therefore $$ \mathbb E[X] = \sum_{i=1}^k \mathbb E[X_i] = \sum_{i=1}^k p^n = k p^n = \frac12 (n-1)! p^n. $$

$\endgroup$
  • $\begingroup$ I definitely agree that my answer was lacking formalism, thank you for pointing it out and providing a neat way of presenting such argument! $\endgroup$ – amator2357 Mar 20 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.