2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is brilliant! Thank you so much. $\endgroup$ – pkwssis Aug 20 at 8:45

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.