Is the phase transition threshold for Hamiltonicity known for the hypercube?

155 Views Asked by At

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?

2

There are 2 best solutions below

0
On

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.

0
On

This has just been resolved and will appear in the SODA 2021 conference. The answer is indeed $p = \frac{1}{2}$.