Sorting sets of binary strings into threes

For each nonempty subset $S$ of $B_n$, consider all of the length $n-1$ substrings formed by removing the first $0$ or $1$ of each element of $S$. For instance, if $$S=\{101,001,010,111\}$$ then the substrings formed by chopping off the first digits are $01,10,11$.

Let $w$ be the lexicographically minimal such substring; in the example, $w=01$. Then $S$ either contains:

  • $1w$ but not $0w$
  • $0w$ but not $1w$
  • $1w$ and $0w$

In our running example, $S$ has both (the third possibility). Let $S’$ and $S^\ast$ be the sets containing all elements of $S$ that don’t end in the substring $s$, as well as $1w$, $0w$, or both according to the other two possibilities above that $S$ does not satisfy. In our example, we have



The blocks $\{S,S’,S^\ast\}$ partition the collection of all nonempty subsets into blocks of size $3$, because starting with $S’$ or $S^\ast$ we get the same three sets as if we start with $S$. This completes the proof.

Finally, to illustrate the construction, here are the five blocks of size $3$ for $n=2$:

  • $\{\{00\},\{10\},\{00,10\}\}$
  • $\{\{01\},\{11\},\{01,11\}\}$
  • $\{\{00,01\},\{10,01\},\{00,10,01\}\}$
  • $\{\{00,11\},\{10,11\},\{00,10,11\}\}$
  • $\{\{00,01,11\},\{10,01,11\},\{00,10,01,11\}\}$

Leave a Reply

Your email address will not be published. Required fields are marked *