# Limiting behavior of the expected number of Hamiltonian cycles in the random graph $G(n, p)$.

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})$$?

• 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. – ericf Mar 19 at 5:50

## 1 Answer

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))$$.

• That is nice, thank you! – amator2357 Mar 20 at 9:20