# HamiltonianCycles in Random Graphs

Lets say we consider the Erdős-Renyi undirected random graph $$G(n,p)$$ with $$V(G) = \{1,2,\cdots,n\}$$ and $$\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V$$.

Is there anything we can say about the probability of the $$G$$ containing a $$HAM$$ Cycle?

This seems like a helpful quantity to figure out for certain computations

Generating random graphs and seeing what fraction contains a $$HAM$$ cycle can of-course be done.

What is the rate of increase of $$P(G\text{ contains }HAMCYC)$$ as $$p$$ increases?

The classical version of this question is for Hamiltonian cycles, but there is probably little difference. I will only consider the version with cycles.

In order for a graph to contain a Hamiltonian cycle, the minimal degree should be at least 2. This is essentially the only obstruction for Hamiltonicity. To state this we need to define the following process:

• For every pair $$\{x,y\} \in [n]$$, let $$\theta_{xy} \sim U([0,1])$$ (independently).
• Define $$G_p = \{ \{x,y\} : \theta_{xy} \leq p \}$$.

By construction, $$G_p \sim G(n,p)$$. As $$p$$ goes from 0 to 1, more and more edges are "exposed". Bollobás proved the following result:

Let $$p_2$$ be the minimum $$p$$ such that the minimal degree of $$G_p$$ is at least 2.

Let $$p_H$$ be the minimum $$p$$ such that $$G_p$$ is Hamiltonian.

With high probability, $$p_2 = p_H$$.

The expected degree of a vertex is $$p(n-1) \approx pn$$. This suggests looking at $$p = c/n$$. A simple calculation shows that for appropriate values of $$c$$, the degree of a vertex has distribution roughly Poisson with expectation $$c$$. In particular, the probability that a vertex has degree less than 2 is roughly $$q = e^{-c}(1 + c)$$. A further calculation shows that these events for different vertices are roughly independent, and so the distribution of the number of vertices of degree less than 2 is roughly Poisson with expectation $$nq$$. In particular, the probability that the minimal degree is at least 2 is roughly $$e^{-nq}$$, for appropriate values of $$c$$. If $$c = \log n + \log \log n + r$$ then $$q = \frac{\log n + \log \log n + r + 1}{e^rn\log n} \approx \frac{e^{-r}}{n}$$, and so $$e^{-nq} \approx e^{-e^{-r}}$$. This suggests the following result:

The probability that $$G(n,p)$$ is Hamiltonian for $$p = \frac{\log n + \log\log n + r}{n}$$ tends to $$e^{-e^{-r}}$$ for constant $$r$$.

If $$r \to -\infty$$ the probability tends to zero, and if $$r \to \infty$$ it tends to one.

This result indeed holds.

You can see a final project of Brunet for some pointers. For more information, consult any decent textbook on random graphs; Hamiltonicity is a classical topic which would be covered in many of them.

• This is brilliant! Thank you so much. – ramseysdream111 Aug 20 '19 at 8:45