10
$\begingroup$

First, let me explain, what I understand by a "Cantor Graph":

it is an infinite, directed graph with self loops and countably many vertices labelled with the natural numbers; every ordered pair of vertices is connected by an arc, whose weight equals the quotient of the labels of its tail and head vertex (the graph is inspired by Cantor's famous proof of the countability of the rationals).

Now, my questions are, given two natural numbers, $m$ and $n$,
1.) how long is the shortest path from $m$ to $n$? and,
2.) how many arcs are on the shortest path from $m$ to $n$?
3.) can the above questions be answered without partially constructing the "Cantor Graph"?

Going, for example, directly from $10$ to $2$ would result in the length of the arc from $10$ to $2$, whose length is 5; going via $5$ would result in a path length of 10/5 + 5/2 = 9/2 and is thus shorter than going via the direct connection.

$\endgroup$
3
  • 3
    $\begingroup$ A simple calculation shows that a single arc is better than any two-length path if and only if $m<4n$. $\endgroup$
    – domotorp
    Nov 24 '13 at 15:15
  • 3
    $\begingroup$ I don't see the connection with Cantor's proof of the uncountability of the reals. Perhaps you meant the countability of the rationals? $\endgroup$
    – Goldstern
    Nov 24 '13 at 20:41
  • 1
    $\begingroup$ Extending domotorp’s simple calculation, if $m=n_0,n_1,\dots,n_k=n$ is a minimal-weight path from $m$ to $n$, then $n_{i-1}\ge 4n_{i+1}\ge n_i\ge n_{i+1}$ and $|n_i-\sqrt{n_{i-1}n_{i+1}+1/4}|\le1/2$ for every applicable $i$. $\endgroup$ Nov 26 '13 at 12:26
9
$\begingroup$

Let me propose an answer to a slightly different question which in some sense is an approximation of the original.

Modified question: Let the vertices of the Cantor graph be the real numbers greater than $1$. And let the weight of the edge $x \rightarrow y$ be $\frac{x}{y}$. What is the shortest path from any $x$ to $1$?

The connection to your original question can be seen by dividing every number with $n$ (if we would like to get from $m$ to $n$).

Answer to the modified question: Let us examine the case where we are using exactly $k$ arcs. We are visiting exactly $k-1$ vertices from $x$ to $1$. Let $\alpha_i$ denote the ratio of the $i$-th and $(i+1)$-th vertex. Thus we are visiting the following vertices: $$ x\, ,\, x \alpha_1 \, , \, x \alpha_1 \alpha_2 \, , \, \dots \, , \, x \prod_{j=1}^{i}\alpha_j \, , \, \dots ,1 $$

The value of this path is exactly: $$x\prod_{i=1}^{k-1} \alpha_i + \sum_{i=1}^{k-1}\frac{1}{\alpha_i} \geq k x^{\frac{1}{k}}$$ Where the inequality is just the AM-GM. Where equality holds if and only if every summand is the same, in other words where every $\alpha_i=x^{-\frac{1}{k}}$. From this it follows that the length of the shortest path is $\min_{k\in \mathbb{Z}^+ }( kx^{\frac{1}{k}} )$. Easy calculations shows that $k$ arcs are optimal if $$\left(1+\frac{1}{k}\right)^{k(k+1)} \leq x \leq \left(1+\frac{1}{k+1}\right)^{(k+1)(k+2)} $$ which bounds are in some sense near $e^{k+1} \leq x \leq e^{k+2}$.

From this it follows that the length of the shortest path is $\Omega(\log{x})$.

$\endgroup$
1
  • $\begingroup$ thanks for your answer; investigating the approximation is a valuable feedback and hopefully the first step towards a solution of the original problem. $\endgroup$ Nov 24 '13 at 19:57

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.