Diameter of a graph consisting of Hamilton cycles

Question

Imagine an undirected graph $G = (V,E)$ with $|V| = n$ nodes. Its unweighted edges $E$ are the union of $h$ random Hamiltonian cycles through all nodes, each generated iid uniformly at random from the set of all Hamiltonian cycles.

What is the expected diameter $D$ of $G$?

The case $h=1$ is trivial and not interesting.

Clearly, $D$ grows strictly monotonically with $n$ as well as with $h^{-1}$. However, I'm not sure of the exact relationship of these variables. I suspect a relationship along the lines of $D = O(\log(n)/h)$.

Answer 1

Purely heuristically, I expect the answer to be $O(\log(n)/\log(h))$.

Why? We can imagine that each vertex has an edge to $2h$ randomly chosen other vertices. Then heuristically we can imagine that there are about $(2h)^d$ vertices at distance $\le d$ from a fixed vertex $v$ (as long as $(2h)^d$ is small compared to $n$). Thus if $(2h)^d \approx n$, we can expect that any fixed pair of vertices $v,w$ are likely connected by some path of length $\le d$. This equation is satisfied when $d \approx \log_{2h}(n) \sim \log(n)/\log(h)$. When $d$ is a small constant factor larger than that, we can heuristically expect there to be an overwhelming probability that any fixed pair of vertices $v,w$ are connected by a path of length $\le d$. Taking a union bound over all pairs of vertices, we can expect that there is $d=O(\log(n)/\log(h))$ such that with overwhelming probability the diameter will be $\le d$.

This is not a proof -- this is just a hand-wavy back-of-the-envelope heuristic estimate.

Answer 2

At least for $h$ constant, taking the union of $h$ uniformly random Hamiltonian cycles is maybe kind of equivalent to taking a uniformly random $2h$-regular graph, whose properties as $n \to\infty$ we know quite well.

One result in this direction is the following. Let $\mathcal G_{n,d}$ denote the uniform probability space over random $d$-regular graph on $n$ vertices. By a result of Kim and Wormald, we have:

If $d\ge4$ is even, then $G \in \mathcal G_{n,d}$ a.a.s. (asymptotically almost surely) has a complete Hamiltonian decomposition.

In other words, with probability tending to $1$ as $n \to\infty$, a uniformly random $2h$-regular graph is the union of $h$ edge-disjoint Hamiltonian cycles.

Of course, if we just take $h$ uniformly random Hamiltonian cycles, they will probably not be disjoint. But they are not too far off either. If $X_{ij}$ is the number of cycles shared between the $i$-th and $j$-th Hamiltonian cycle, then $X_{ij} \sim \operatorname{Poisson}(2)$. So as long as $h$ is constant, the number of overlapping edges is $O(1)$ a.a.s., and with constant probability there are none.

Another reason not to care about the overlaps is that I'm pretty sure that a different result is also true: if $\mathcal G_{n,d}'$ is the corresponding probability space to $\mathcal G_{n,d}$ of $d$-regular loopless multigraphs (allowing parallel edges), then for even $d$, $G \in \mathcal G_{n,d}'$ a.a.s. has a decomposition into Hamiltonian cycles that are no longer edge-disjoint. (The paper above mentions this for $d=4$, but doesn't say anything one way or the other about larger $d$; I think the same methods would solve that problem.)

Since all unions of $h$ Hamiltonian cycles are equally probable outcomes of sampling from $\mathcal G_{n,2h}'$, this would tell us at results true a.a.s. of $\mathcal G_{n,2h}'$ are also true a.a.s. of this random graph model. This is nice, because many proofs about $\mathcal G_{n,d}$ go through multigraphs first anyway, and then take into account the probability that the graph is simple. In particular, this is true of the result below.

A result of Bollobás and de la Vega gets the following bounds on the diameter of $\mathcal G_{n,r}$ (switching notation, they use $r$ for degree):

Theorem 1. Let $r \ge 3$ and $\epsilon>0$ be fixed and define $d=d(n)$ as the least integer satisfying $$(r-1)^{d-1} \ge (2+\epsilon) rn \log n.$$ Then a.e. $r$-regular graph has diameter at most $d$.

Theorem 3. The diameter of a.e. $r$-regular graph of order $n$ is at least $$\lfloor \log_{r-1} n\rfloor + \left\lfloor\log_{r-1} \log n - \log_{r-1}\frac{6r}{r-2} \right\rfloor + 1.$$

Set $r = 2h$ and that's that.