Partition of $\mathbb{F}_2^n$?

Question

Consider an undirected graph $G$ with $n$ nodes denoted by $i$, $i \in [n] = \{1,2,...,n\}$. Denote the set of neighbours of node $i$ in the graph by $N(i)$.

Given that there exists a set $\mathcal{I} \subset \{0,1\}^n$, $|\mathcal{I}|=2^k$, that has the following property. For any $x,y \in \mathcal{I}$, $x \ne y$ and $z=x+y$ we must have, $$z_i=1 \implies wt(z[N(i)]) \geq 1, \forall i \in [n]$$ Show that there exists a partition $\mathcal{I}_1, \mathcal{I}_2, ..., \mathcal{I}_{2^{n-k}}$ of $\mathbb{F}_2^n$ . Such that each set has the above property.

Notation:

addition is considered modulo-2

$x_i$ denotes $i^{th}$ component of vector $x$.

$x[\mathcal{A}]$ for any set $\mathcal{A} \subset [n]$ denotes the $|\mathcal{A}|$ size vector consisting of the corresponding bits of $x$.

$wt(x)$ denotes the number of $1$'s in vector $x$.

Obervation:

If the set $\mathcal{I}$ has the above property then the set $\{x+v | x \in \mathcal{I} \}$ for any fixed $v \in \mathbb{F}_2^n$ also has the above property.

Answer 1

This is just some long comments:

Let $S$ be an independent set of the graph. If $\mathcal I$ is any set with this property, and $v$ is any vector supported entirely on that set, then $\mathcal I+v$ and $v$ are disjoint. Indeed, let assume $x+v = y$, then since $v\neq 0$, $x\neq y$, but $x+y=v$ and $v$ does not satisfy the desired property.

So if $k \geq n$ minus the size of the maximum independent set, we are done.

Similarly, imagine we have a set of $\leq k$ cliques that contain all the vertices. Then we can partition the set of vectors into parts according to the sums over the cliques - one part where the sums over all the cliques are $0$, one part where the sum over the first clique is $1$ and the rest are $0$, and so on.

So we are done in every graph where the largest independent set is as big as the smallest clique cover, or even when the difference is at most $1$.

I think this might be more of a graph theory problem than an algebra problem.

Answer 2

The answer to this question turns out to be negative i.e. in general it is not possible to partition the space $\mathbb{F}_2^n$ such that each partition has that property.

Consider the graph on $\mathbb{F}_2^n$ with any two nodes $x,y \in \mathbb{F}_2^n$ adjacent iff for $z=x+y$, $z_i = 1$ and $wt(z[N(i)])≥1$ for any $i \in \{1,2,...,n\}$. This graph is called the confusion of the graph $G$, $\mathbb{C}(G)$

Thus the set $\mathcal{I}$ is an independent set of $\mathbb{C}(G)$. Now consider the largest independent set $\mathcal{I}$.

Consider the confusion graph of the $5$-cycle. It can be shown that the maximum independent set of the confusion graph of $C_5$ is of size $5$. Therefore it is not possible to cover the whole set (32 vertices) using sets of size $5$.