Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider infinite digraphs whose vertices are the integers $\mathbb Z$, with the property that there are exactly two arcs coming out of each vertex. (There is no restriction on the number of in-coming arcs.)

The question: is there such a digraph such that for $m,n\in\mathbb Z$, with $m<n$, there is a directed path from $m$ to $n$ of length $O(\log(n-m))$?

This problem is an abstraction of one arising in data structures (imagine a linked list with two links per node). Years ago I was confident I had solved it, but I can't find my notes and right now I only see $O(\log(n-m)^2)$.

In addition to existence, it would be nice if there is an effective algorithm for following the path, i.e. given that you are at $m$ you can quickly figure out how to get to $n$ in $O(\log(n-m))$ steps. Define "quickly" as you like.

share|improve this question
    
[Strictly speaking $O(\log(n-m))$ is impossible when $n-m = 1$... But it seems we're both treating this as $O(1 + \log(n-m))$.] –  Noam D. Elkies Sep 12 '11 at 1:01
add comment

1 Answer

up vote 26 down vote accepted

Yes, such a directed graph exists, with a "quickly" computable path of length $O(\log|n-m|)$ from $m$ to $n$ for any distinct integers $m,n$.

I'll first construct a digraph with this property but with each vertex having out-degree at most $8$, then show how to get from it a digraph of out-degree $2$.

Denote by $v(x)$ the $2$-adic valuation of the integer $x$, which is the unique integer $e \geq 0$ such that $x/2^e$ is an odd integer; conventionally $v(0) = \infty$.

The graph edges emanating from $x$ will be as follows. If $x$ has valuation $e>0$ then $$ x \rightarrow x \pm 1, \phantom+ x \pm 2^{e-1}, \phantom+ x \pm 2^e, \phantom+ x \pm 3\cdot 2^e. $$ If $x$ is odd, omit $x \pm 2^{e-1}$ so $x$ goes only to $x \pm 1$ and $x\pm 3$. If $x=0$ then $x\mapsto \pm 1$ only.

Then:

(i) For each $e \geq 0$, the integers of valuation $e$ constitute an arithmetic progression of common difference $2^{e+1}$. We can get from such $x$ to $x \pm 2^{e+1}$ in two steps: if $e=0$ then add or subtract $1$ twice; if $e>0$ then add or subtract $2^{e-1}$ and then $3 \cdot 2^{e-1}$.

(ii) If $v(x) = e$ and $|n-m| \leq 2^e$ we can get from $m$ to $n$ in at most $2 \phantom. \log_2 |n-m| + 1$ steps. Indeed if $|n-m| = 2^e$ one step suffices, so assume $|n-m| < 2^e$ and then $|n-m| \in [2^d, 2^{d+1})$ with $d < e$. By symmetry we may assume $n>m$. Then $$ m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d $$ in $d+1$ steps, and then in a further $d - v(n)$ steps we reach $n$ by writing $$ n = m + 2^d + 2^{d-1} \pm 2^{d-2} \pm 2^{d-3} \pm \cdots \pm 2^{d-v(n)}. $$

(iii) If $v(m) = e < f$, and $n$ is the integer of valuation exactly $f$ that's nearest to $m$, then we can get from $m$ to $n$ in $f-e$ steps. At the $i$-th step, add either $\pm 2^{e+i-1}$ or $\pm 3 \cdot 2^{e+i-1}$ to reach a number of valuation exactly $e+i$; there are two choices, so take the one closer to $n$. The distance to $n$ always stays below $2^f$ so at step $f-e$ we hit $n$.

(iv) Finally, suppose $m$ is odd and $|n-m| \in [2^k, 2^{k+1})$. Find $n'$ of valuation $k$ such that $|n-n'| \leq 2^k$. Thus $|m-n'| < 3 \cdot 2^k$. By (iii), in $k$ steps we get from $m$ to some $n_1$ such that $|m-n_1| < 2^k$ and $v(n_1) = k$. So either $n_1=n'$ or $n_1 = n' \pm 2^{k+1}$, and in the latter case we reach $n'$ in a further two steps using (i). Then in at most $2k+1$ further steps we reach $n$ using (ii).

We are done, in a total of $3 \phantom. \log_2 |n-m| + O(1)$ steps, because if $m$ is not odd then we can use our first step to move to the odd number $m \pm 1$ closer to $n$.

Now to get from out-degree $8$ down to $2$: for each $x \in {\bf Z}$ choose $f_i(x)$ for $i=0,1,2,\ldots,7$ so that $\{f_0(x),f_1(x),f_2(x),\ldots,f_7(x)\}$ is the set of integers reachable from $x$ (with repetitions if $x$ is odd or zero). Define a new graph of out-degree $2$ as follows: write every integer as $8x+i$ for some $x \in \bf Z$ and $i\in\{0,1,2,\ldots,7\}$, and then $8x+i \rightarrow 8f_i(x)$ and $8x+i \rightarrow 8x+i'$ where $i'=0$ if $i=7$ and $i'=i+1$ otherwise. That is, we partition $\bf Z$ into directed $8$-cycles, which consumes only one outgoing edge per integer and leaves us with $8$ further edges per cycle to assign as we wish, letting us use our graph of out-degree $8$. Each step of our algorithm then expands to at most $8$, because we might have to take as many as $7$ steps cycling around until we reach the correct $i$ to make the next step in our original graph, and then at the end we might still have to spend an extra $7$ steps to reach the target $n$ within its cycle. But that's still at most $24 \phantom. \log_2 |n-m| + O(1)$ steps, and still with an explicit and "quick" algorithm.

[EDIT we can reduce $3 \phantom. \log_2 |n-m| + O(1)$ to $\frac52 \log_2 |n-m| + O(1)$ by compressing $$m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d$$ to $$m \rightarrow m + 1 \rightarrow m + 4 \rightarrow m+16 \rightarrow \cdots \rightarrow m+2^d,$$ and there's probably another multiple of $\log_2|n-m|$ to be saved by permuting $f_0(x),f_1(x),f_2(x),\ldots,f_7(x)$ to reduce the number of steps spent within directed $8$-cycles.]

share|improve this answer
    
That's great! My recollection is that there is a solution with one edge going just to the next vertex (x->x+1), and the other edge going forward some distance. Can you see that, or rule it out? –  Brendan McKay Sep 4 '11 at 14:48
    
Don't you need edges going backward? Gerhard "Ask Me About System Design" Paseman, 2011.09.04 –  Gerhard Paseman Sep 4 '11 at 17:42
    
@Brendan: i) Thanks! ii) Without backtracking I only see the same $\log^2$ construction that I guess you found, but I can't immediately prove that the directed distance cannot be $O(\log(n-m))$. $$ $$ @Gerhard: The original question specified $m<n$, and backwards edges aren't necessary to get from any integer to any larger integer, though they might be needed to achieve the desired $O(\log(n-m))$ distance. –  Noam D. Elkies Sep 4 '11 at 17:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.