Existence of a set of binary vectors which fulfill certain constraints

37 Views Asked by At

The following problem seems somewhat abstract but it would be nice to get it (dis)proven. Assume we are given a set $\mathcal B$ of $n$ binary vectors $\boldsymbol b_1,\dots,\boldsymbol b_n$, each of dimension $2^n-3$, i.e., \begin{align} \boldsymbol b_i\in \{0,1\}^{2^n-3}, \ 1\le i\le n. \end{align} The assumption is now that there is no set $\mathcal B$ s.t. the following constraints are fulfilled: \begin{align} \langle \boldsymbol b_i,\boldsymbol b_i\rangle&\overset{!}{=}2^{n-1}-1, \ 1\le i\le n, \tag{1} \\ \langle \boldsymbol b_i,\boldsymbol b_j\rangle&\overset{!}{=}2^{n-2}-1, \ i\neq j. \tag{2} \end{align} In words, $(1)$ ensures that every vector has exactly $2^{n-1}-1$ ones and $(2)$ ensures that each vector pair has exactly $2^{n-2}-1$ ones in common.

For $n=2$ it is true, since for $\mathcal B=\{\boldsymbol b_1,\boldsymbol b_2\}$, $\boldsymbol b_i\in\{0,1\}$, we only have $1$ possibility, i.e., $$ \mathcal B =\{0,1\}, $$ which does not adhere $(1)$.

It is also true for $n=3$, since if $(1)$ is adhered, then every $\boldsymbol b_i$ is of dimension $5$ with $3$ ones. If we now take two vectors $\boldsymbol b_1$, $\boldsymbol b_2$ which adhere $(2)$, then the vector $\boldsymbol b_1 + \boldsymbol b_2$ has no zero entries. If any $\boldsymbol b_3$ adheres $(1)$ it has $3$ ones and thus has to have more than a single one in common with $\boldsymbol b_1$ or $\boldsymbol b_2$, which violates $(2)$.

Intuitively it seems to me that this principle is easily extendable to any $n>3$, either through induction or maybe just the pigeonhole principle, but I cannot figure out how. There may also be a nice counter example.

1

There are 1 best solutions below

0
On BEST ANSWER

I found a counter example for n=4:

[{0, 1, 2, 3, 4, 5, 6}, {2, 3, 6, 7, 8, 10, 12}, {3, 4, 5, 7, 9, 10, 11}, {0, 1, 4, 7, 8, 9, 12}])

Where I only wrote the indices of the 'true' (or 1) entries for each vector. So, {0, 1, 2, 3, 4, 5, 6} could also be written as (1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0)

Cheers