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$.

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.

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)$.

Consider a set $\mathcal{I} \subset \{0,1\}^n$ 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$$

Given that there exists one such set $\mathcal{I}$, $|\mathcal{I}| = 2^k$, how do I find partitions of $\mathbb{F}_2^n$ of size $2^k$ that has the above property.

Notation:

$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$.

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$.