4
$\begingroup$

If $x$ and $y$ are both $n$-bit strings then their Hamming distance $d_H(x,y)$ is the number of positions in which they differ.

Suppose we write out the set of all $n$-bit strings in some order $s_1, \ldots, s_{2^n}$. Now define the distance of two strings with respect to this order as $d_S(s_i,s_j) = \min \{ i-j \bmod 2^n, j-i \bmod 2^n \}$. I consider the ordering to be cyclic.

I would like an ordering of strings that approximately preserves Hamming distances in the following way:

There is a "small" function $f$ such that, for all $n$-bit strings $x,y$, $d_S(x,y) \le f( d_H(x,y) )$.

In other words, strings of Hamming distance $\delta$ are within $f(\delta)$ distance in the ordering. I want $f$ to be as small as possible. I am also fine if this bound only holds for small $\delta$.

I have found some results on "distance-preserving Gray codes" which have a similar property (one such paper cited below), but it's closer to the converse of what I want. These gray codes have the property that if $d_S(x,y) \le \delta$ then $d_H(x,y) = d_S(x,y)$. In other words, nearby strings in the gray code are nearby in Hamming space, but it doesn't guarantee that all nearby points in Hamming space are also nearby in the gray code.

Binary gray codes with long bit runs: Luis Goddyn, Pavol Gvozdjak. Elect. J of Comb. 2003

$\endgroup$
  • 1
    $\begingroup$ Why $\bmod2^n$? Isn't $0\le|i-j|\lt2^n$? $\endgroup$ – joriki Apr 12 '16 at 22:38
  • 1
    $\begingroup$ Ah, I think I just mean min $\{ i-j \bmod 2^n, j-i \bmod 2^n \}$, since I consider the ordering to be cyclic. Fixed now. $\endgroup$ – mikero Apr 12 '16 at 22:48
4
+50
$\begingroup$

No, unfortunately there isn't. Observe first of all that we can always choose $f$ to be linear when $n$ is fixed: if making one edit in some codeword causes a displacement of at most $f(1)$ in our cyclic ordering, then making two edits causes a displacement of at most $2\cdot f(1)$, making three edits causes a displacement of at most $3\cdot f(1)$, and so on. Thus, for fixed $n$ the function $f$ can be considered to be small.

However, we shall see that the value of $f(1)$ grows exponentially in $n$. Note that for $\delta = 1$ the question is precisely that of determining the circular bandwidth of the hypercube graph $Q_n$, which is defined as follows:

Definition. For $n,\ell\in\mathbb{N}$ we define $C_{n,\ell}$ to be the graph on the vertex set $\{0,\ldots,n-1\}$ where two vertices $i,j\in\{0,\ldots,n-1\}$ are joined by an edge if and only if $$\min(i - j \bmod n \:, \: j-i \bmod n) \leq \ell. $$ For instance, $C_{n,1}$ is simply the cycle on $n$ vertices, and $C_{n,\left\lfloor\frac{n}{2}\right\rfloor}$ is the complete graph.

Now the circular bandwidth of a graph $G$ on $n$ vertices is defined as the minimum value of $\ell$ such that $G$ is isomorphic to a subgraph of $C_{n,\ell}$. The circular bandwidth of $G$ is denoted $\text{cbw}(G)$.

The circular bandwidth has the same order of magnitude as the regular (linear) bandwidth $\text{bw}(G)$:

  • On the one hand, clearly we have $\text{cbw}(G) \leq \text{bw}(G)$.
  • On the other hand, it is not too hard to show that $\text{bw}(G) \leq 2\cdot \text{cbw}(G)$ holds. The following proof is taken from P. Erdős, P. Hell, P. Winkler, Bandwidth versus bandsize, Graph theory in memory of G. A. Dirac, Annals of Discrete Mathematics 41 (1989) 117-130, though the result might have been known earlier. If $n$ is even, we number the vertices of the cycle graph $C_{n,1}$ in the following manner: $$1,3,5,7,\ldots,n-3,n-1,n,n-2,\ldots,6,4,2.$$ Similarly, if $n$ is odd we number the vertices of the cycle graph $C_{n,1}$ by $$1,3,5,7,\ldots,n-2,n,n-1,n-3,\ldots,6,4,2.$$ This shows that the bandwidth of $C_{n,1}$ is at most 2. Thus, the bandwidth of the graph $C_{n,\ell}$ is at most $2\ell$, which shows that $\text{bw}(G) \leq 2\cdot\text{cbw}(G)$ holds for any graph $G$.

The (linear) bandwidth of the hypercube graph $Q_n$ is known: see original paper by Harper, Wikipedia and OEIS sequence A036256. Specifically, we have $$ \text{bw}(Q_n) = \sum_{m=0}^{n-1} \binom{m}{\left\lfloor\frac{m}{2}\right\rfloor}. $$ Of course these central binomial coefficients grow exponentially in $n$. Indeed, OEIS gives the following approximation: $$ \text{bw}(Q_n) \sim \frac{2^{n+\frac{3}{2}}}{\sqrt{\pi n}} \cdot \left(1 + \frac{(-1)^n}{12n}\right). $$ By the above estimate, the circular bandwidth is at least half of this, so it also grows exponentially. This shows that you cannot do much better than the lexicographic order. (Interestingly, Harper claims that the lexicographic order minimises the average absolute difference of numbers assigned to neighbouring vertices, rather than the maximum absolute difference for the linear bandwidth.)


In summary: $f$ is linear in $\delta$ but exponential in $n$.

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