<p>No. Given any linear ordering of the <span class="math-container">$n$</span>-bit strings, find a sequence of at most <span class="math-container">$n+1$</span> strings going from the first string in the ordering to the last string in the ordering by single-bit changes per step. Some two adjacent strings <span class="math-container">$x$</span> and <span class="math-container">$y$</span> in this sequence must be at least <span class="math-container">$2^n/n$</span> steps apart from each other in the ordering. But then, unless your definition of "far" only allows linearly many strings to be far apart from each other, there must be some <span class="math-container">$z$</span> that is far from <span class="math-container">$x$</span> and <span class="math-container">$y$</span> but between them in the ordering. So changing one bit from <span class="math-container">$x$</span> to <span class="math-container">$y$</span> reverses the ordering with <span class="math-container">$z$</span>.</p>

CC BY-SA 4.0
2018-12-15T18:39:57.313Z
2018-12-15T20:24:05.477Z
2018-12-15T20:24:05.477Z
David Eppstein
<p>I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the strings.</p>

<p>For example, lexicographic order does not satisfy this property because it may be possible to change the order of the string by changing just one bit.</p>

<p>On the other hand, order according to the number of ones is not good either because it only works for linear number of strings.</p>

<p>Is there such an ordering?</p>

<p>Edit: A solution which only works for random strings is also of interest to me.</p>

<co.combinatorics>
Stable order on binary strings
user2316602
# Stable order on binary strings

(Asked by: username_0 on 2018-12-15)

I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the strings.

For example, lexicographic order does not satisfy this property because it may be possible to change the order of the string by changing just one bit.

On the other hand, order according to the number of ones is not good either because it only works for linear number of strings.

Is there such an ordering?

Edit: A solution which only works for random strings is also of interest to me.

**Tags:** co.combinatorics

---

## 1 answers

### Answer by username_1 on 2018-12-15. Score: 7 | Accepted answer

No. Given any linear ordering of the $n$-bit strings, find a sequence of at most $n+1$ strings going from the first string in the ordering to the last string in the ordering by single-bit changes per step. Some two adjacent strings $x$ and $y$ in this sequence must be at least $2^n/n$ steps apart from each other in the ordering. But then, unless your definition of "far" only allows linearly many strings to be far apart from each other, there must be some $z$ that is far from $x$ and $y$ but between them in the ordering. So changing one bit from $x$ to $y$ reverses the ordering with $z$.


---

