1
$\begingroup$

Pretty much just the question in the title. Given a random graph formed from the hypercube, is it known what the phase transition (edge probability) is to find a Hamiltonian path with probability 1 in the limit? It is known for Erdos-Renyi random graphs, but I can't seem to find if anyone has shown this.

More generally, has anyone shown Hamiltonian phase transitions for random graphs on centrally symmetric polytopes?

$\endgroup$
1
$\begingroup$

As a partial answer, a very sharp threshold for $2$-connectivity is $p = \frac12 + \frac{\ln n}{2n}$, where $n$ is the dimension of the hypercube. More precisely, by Theorem 1.1 in this paper, if $p = \frac12 + \frac{\ln n}{2n} + \frac cn$, then the random subgraph of the hypercube is $2$-connected with probability tending to $e^{-e^{-2c}}$ as $n \to \infty$, and w.h.p. $1$-connected otherwise. This is also the threshold for having minimum degree $2$.

A related result by Bollobás shows that if we add random edges of the hypercube one at a time, the hitting time for having no isolated vertices, for being connected, and for having a perfect matching are the same. (In particular, the threshold $p=\frac12$ is the same for both.)

Similarly, I would not be surprised if it turned out that - just as in ordinary random graphs - having minimum degree $2$ were enough to guarantee a Hamiltonian cycle, in which case the threshold in the first paragraph above would be the correct answer. It doesn't seem like anyone knows whether this is true.

$\endgroup$

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.