Say I have set of $m$ Boolean vectors $$B = \{x_1,\ldots, x_m\}$$ where $x_i \in \{0,1\}^n$.

We know the following about the vectors $x_i \in B$:

(i) $\|x_i\| \in [1,n-1]$ for all $x_i \in B$ (at least 1 non-zero coordinate and one zero coordinate)

(ii) $d(x_i, x_j) \geq 1$ for all $x_i, x_j \in B$ (each vector is distinct)

(iii) $d(x_i, x_j) \leq r$ for all $x_i, x_j \in B$ (all vectors differ by at most $r$ coordinates)

Here $d(x_i, x_j) = \|x_i - x_j\| = \sum_{k=1}^{n} 1[x_{i,k} \neq x_{j,k}]$ is the Hamming distance between $x_i$ and $x_j$.

My question is the following: Given a vector $x_i \in B$, what is the maximum number of coordinates where $x_i$ is false, but at least $t$ of the other vectors are true? In other words, I am looking for an upper bound on the size of the following set:

$$Z(x_i, t) = \left\{k =1,\ldots, n ~\Big|~ x_{i,k} = 0 ~\text{and}~ \sum_{j \neq i} x_{j,k} \geq t \right\} $$

for values of $t \in [1, |B| - 1]$.

Note: I can derive the following upper bound when $t = 1$ (see a related post for a simpler problem on math.SE):

$$|Z(x_i, 1)| \leq \frac{r - \|x_i\| + \max_{j \neq i} \|x_j\|}{2}$$

However, I'm not sure how to extend this to settings where $t \geq 2$ (or whether this is actually the best bound I could produce for $t = 1$). Any help would be appreciated.


**Too long for a comment:**If I didn't misunderstand the question, the following set is a counterexample to your bound with $r=4,|x_1|=1,|x_j|=2,2\leq j\leq 7$ and $Z(x_1)=4.$

$$ \begin{array}{lr} x_1 & 10000\\ x_2 & 01100\\ x_3 & 01010\\ x_4 & 01001\\ x_5 & 00110\\ x_6 & 00101\\ x_7 & 00011 \end{array} $$


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.