2
$\begingroup$

The following theorem is from Alon&Spencer's The probabilistic method, in the beginning of chapter 2:

Theorem 2.1.1: There is a tournament $T$ with $n$ vertices and at least $\frac{n!}{2^{n-1}}$ Hamiltonian paths.

Briefly the theorem is proved by looking at $X_\sigma$ the indicator random variable for a permutation $\sigma$ giving a Hamiltonian path, that is, satisfying $(\sigma(i),\sigma(i+1))\in T$ for $1\leq i \lt n$. Then

$\sum \mathbb{E}\left[X_\sigma\right] = \frac{n!}{2^{n-1}}$.

I don't understand where did this value ($\frac{n!}{2^{n-1}}$) came from! could someone explain it please?

$\endgroup$
  • $\begingroup$ Please give a source for the theorem and proof. $\endgroup$ – saulspatz Apr 29 '18 at 17:15
1
$\begingroup$

The argument is to construct a tournament by randomly orienting the edges of $K_n.$ Say the edge goes from the greater number to the smaller with probability $1/2,$ assuming that the vertices are the integers $1,\dots,n.$ Then the probability that a given permutation of the vertices is a Hamilton path is just $2^{1-n},$ leading to the expectation you have given.

$\endgroup$
1
$\begingroup$

Here is how I figured it out,

For each permutation of the vertices, the probability that this permutation represents a hamiltonian path is the probability that each edge points in the correct direction as the previous one, and since the orientation of each edge is chosen indepently then this probability is simply the product of probabilities of the orientation of $(n-1)$ edges. So the probability of the event that a permutation contains a hamiltonian path is $\frac{1}{2^{n-1}}$.

Now since we have $n!$ possible permutations thus the summation of $\mathbb{E}\left[X_\sigma\right]$ will be $\frac{n!}{2^{n-1}}$.

$\endgroup$
  • 2
    $\begingroup$ This is the expectation, not "the whole probability." Notice that it will be greater than $1$ if $n>2.$ $\endgroup$ – saulspatz Apr 29 '18 at 21:22
  • $\begingroup$ Sorry, my mistake. I fixed it now. $\endgroup$ – Dorgham Apr 30 '18 at 23: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.