7
$\begingroup$

This question derives from a PPCG coding challenge I posed previously but despite asking on math.se and offering a bounty, no progress has been made.

For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of length $n$ which contains the count of the number of $1$s in each substring of length $n$ of $S$. For example, if $n=3$ and $S = 01010$ then $L=[1,2,1]$. We call $L$ the counting array of $S$.

We say that two strings $S1$ and $S2$ of the same length match if their respective counting arrays $L1$ and $L2$ have the property that $L1[i] \leq 2*L2[i]$ and $L2[i] \leq 2*L1[i]$ for all $i$.

Problem

For increasing $n$ starting at $n=1$, we want to compute the size of the largest set of strings, each of length $2n-1$ so that no two strings match.

Known answers

For $n=1,2,3,4,5$ the optimal answers are $2,4,10,16,31$.

For $n=6,7,8,9,10$, the best known values are $47, 76, 112, 168, 235$ from a combination of the answers of joriki and Peter Taylor.

The question

Plotting these values they appear to be subexponential but it is hard to say much more than that. This leads to the question:

How do optimal solutions scale with $n$?

$\endgroup$
2
  • $\begingroup$ An experimental observation: let $G_n$ be the directed graph with strings as vertices, and an edge from $S_1$ to $S_2$ if $L_1\leqslant 2L_2$. Then the transitive reduction of $G_n$ contains a "dominating" cycle: of order $7$ for $n=2$, of order $29$ for $n=3$, of order $120$ for $n=4$, ... $\endgroup$ Aug 21, 2015 at 20:39
  • 1
    $\begingroup$ Here's an idea for dealing with strings that are not outrageously sparse: take a string, split it up into blocks of length $n/10$, say. For each block, store $\lfloor 10\log_2$(weight)$\rfloor$. If two strings have the same weight vector (and are not ridiculously sparse), then they match. Since there are only $(\log n)^{20}$ weight vectors, this should give a good bound on non-sparse independent sets... $\endgroup$ Aug 21, 2015 at 22:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.