What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each other?
Remarkably, I expect the answer to be $(C±o(1)) / \sqrt n$, and that if such $G$ has a Hamilton cycle, then with high probability, the cycle is unique and can be found in polynomial time.
Edit (thanks Brendan McKay for the suggestion): Equivalently, given a random $\frac{2}{3}n$ vertex cubic graph (weighted by the number of its perfect matchings) and a random perfect matching on it, we want the probability of existence of a Hamilton cycle extending the matching. Also, I do not expect the weighting to change the probability by more than a constant factor.
Finding Hamilton cycles (i.e. a cycle containing all $n$ vertices) is NP complete in general, but the problem is easy on random graphs as we need lots of edges to avoid local obstructions like a vertex of degree 0 or 1, or three degree 2 vertices joining at a vertex. But what if we could eliminate local obstructions, but then reduce the number of edges to the threshold for Hamiltonicity? We would be expect the problem to be hard (like random $k$-SAT), except that here we get special structure.
The motivation for our restriction on low degree vertices is that minimum degree 2 (or higher) is required for Hamiltonicity, and degree 2 vertices at distance 1 or 2 to each other can be merged to reduce the problem to a simpler graph.
$\frac{4}{3} n$ edges ($n$ divisible by 3) is the minimum for our restriction on the low degree vertices. We should still get $n^{Θ(n)}$ non-isomorphic graphs. ($o,O,Θ,Ω,ω$ are from Big O Notation.) However, the low average degree regularizes their local structure. For a random graph with $Θ(n)$ edges (and presumably here as well), and except for a small expected number of vertices, the local structure is that of a tree. And up to isomorphism (but with many symmetries), there is only one way to set up the tree here.
Locally, degree 3 vertices are joined in long chains, with degree 2 vertices on the side, so a Hamilton cycle must include every other edge in each chain (giving us two choices per chain). Globally, the chains become cycles, and $G$ has a disjoint cycle cover for vertices iff all of the chains have an even length.
Let us assume (formalizing and proving this will answer the question) that the chains resemble a random 2-regular graph and the resulting cycle covers are also sufficiently random. The expected number of cycles in random 2-regular graphs is $(1±o(1)) \frac{1}{2} \log n$, and the probability of having just one cycle is $(1±o(1)) e^{3/4} \sqrt{\frac{π}{4n}}$ (and with a roughly Poisson-Dirichlet distribution PD(0,1/2) for cycle sizes). At $k$ cycles (chains), the probability that all are even should be $2^{-k±O(1)}$, which cancels out with $2^k$ possible assignments (with the expected number of chains not large enough to expect multiple Hamilton cycles if there are any), leaving us with $Θ(n^{-1/2})$ Hamilton cycle probability.
The Hamilton path existence probability should be $Θ(n^{-1/4} \log^2 n)$, which should also hold if the endpoints cannot have degree 2 in $G$. This is based on the probability that at most 2 cycles (chains) have odd length (note that the number odd chains is even) and that the two odd cycles are, with $Ω(1)$ probability, large enough for a (presumably) sufficient number of connection possibilities.
For $\frac{4}{3} n + Θ(n)$ edges (at least for large enough $Θ(n)$), I expect that:
- The probability of a Hamilton cycle is $Θ(1)$.
- The obstructions to having a Hamilton cycle are primarily local, with the main obstruction (all but $O(n^{-1})$ probability) being an odd cycle of degree 3 vertices with degree 2 vertices on the side.
- There are typically $2^{Ω(n)}$ Hamilton cycles if there are any.
- With high probability, a Hamilton cycle can found or its non-existence certified in linear time (here).
- All of the above still holds if we also require that the number of degree 2 vertices is $n/3$.
I am also interested in partial results, like $n^{-O(1)}$ probability, or a numerical confirmation of $(C±o(1)) / \sqrt n$ on large enough graphs.
