1
$\begingroup$

So we have that 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}$ for $n \geq 3$.

We now want to find lim$_{n\to \infty}\mu_{n}(\frac{c}{n})$, where $c$ is a constant.

Ok, we know that $0 \leq p \leq 1$ $\implies$ $0 \leq \frac{c}{n} \leq 1 \implies c \geq 0$ and $n \geq c$. I'm not sure how one should think about the last constraint, i.e. that $n \geq c$. So when we think about evaluating lim$_{n\to \infty}\mu_{n}(\frac{c}{n})$ do we just fix some $c \geq 0$? But then, for instance if take $c = 111$ and let $n$ go to infinity, for $n<111$ we're considering events with probability $>1$ which doesn't make sense. Or does it? Or should we restrict $c$, s.t. $0\leq c \leq 3$, so the constraints above are always satisfied?

How would we then go about finding lim$_{n\to \infty}\mu_{n}(\frac{c}{n})$?

$\endgroup$
  • $\begingroup$ Since we are only considering the limit when n goes to infinity we can pick any c and assume that n is bigger than it. $\endgroup$ – ericf Mar 19 at 5:50
1
$\begingroup$

We can use Stirling's approximation, in the form $$ n! \sim \sqrt{2 \pi n} \left(\frac ne\right)^n. $$ Here, we have $$ \mu_n(\tfrac cn) = \frac{n! \cdot (\frac cn)^n}{2n} \sim \sqrt{\frac{\pi}{2n}} \left(\frac ne\right)^n \left(\frac cn\right)^n = \sqrt{\frac{\pi}{2n}} \left(\frac ce\right)^n. $$ Therefore,

  • for $c < e$, $\mu_n(\frac cn) \to 0$ exponentially quickly.
  • for $c = e$, $\mu_n(\frac cn) \sim \sqrt{\frac{\pi}{2n}}$, so $\mu_n(\frac cn) \to 0$ again, but at a reduced rate.
  • for $c > e$, $\mu_n(\frac cn) \to \infty$ exponentially quickly.

In a finer parametrization $$ p(n) = \frac{en + \frac12\ln n + f(n)}{n^2}, $$ the same approximation shows that $$ \mu_n(p(n)) \sim \sqrt{\frac\pi 2} e^{f(n)} $$ and the behavior of $f(n)$ determines the behavior of $\mu_n(p(n))$.

$\endgroup$
  • $\begingroup$ That is nice, thank you! $\endgroup$ – amator2357 Mar 20 at 9:20

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.