3
$\begingroup$

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)$.

$\endgroup$

migrated from cs.stackexchange.com Mar 28 '17 at 20:39

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ You need to clarify what exactly you mean by $O$ here: is $h$ fixed? If not, how does it grow in relation to $n$? "True" two-parameter Landau symbol are notoriously awkward. $\endgroup$ – Raphael Mar 29 '17 at 6:44
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\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.