Is $F(F(A)) = A$ for every k-hypercube where k is odd?

Question

Suppose we have a k-hypercube $(Q_k)$ where $k$ is an odd integer.

Define $F(A)$ for $A \subseteq V$ as the set of all vertices such that has odd number of edges to the set $A$.

Is it true that $F(F(A)) = A$?

Answer 1

Yes, let $M$ be the adjacency matrix of $Q_k$ over $F_2$, $V$ be the $F_2$-vector space with basis $(v_u)$ indexed by the vertex set of $Q_k$, denote $v_A=\sum_{u\in A}v_u$. We see that $Mv_A=v_{F(A)}$ so $v_{F(F(A))}=M^2v_A$, we just need to prove that $M^2$ is an identify matrix. The $(u,w)$ entry of $M^2$ is the number of walks of length $2$ from $u$ to $w$, when in $F_2$, it is $0$ if there are an even number of such walks and $1$ if otherwise:

-If $u=w$, there is $k$ walks of length $2$, go from $u$ to one of the adjacency vertex of $u$, and go back to $u$, because $k$ is odd, the $(u,u)$ entry is $1$.

-If $d(u,w)=1$ or $d(u,w)>2$, there is no walks of length $2$ from $u$ to $w$, so the $(u,w)$ entry is $0$.

-If $d(u,w)=2$, there are $2$ walks of length $2$ from $u$ to $w$, so the $(u,w)$ entry is also $0$.

So $M^2$ is the identify matrix as we want.

Answer 2

• Lemma 1: $\space F(U \Delta V) = F(U) \Delta F(V)$.

  Prove: By using $S_1 = S_2 \iff S_1 \subseteq S_2 \land S_2 \subseteq S_1$ we can prove this equality.

  1. Suppose $c \in F(U \Delta V)$, we know $c$ has odd number of neighbors in $U \Delta V$ by the definition of $F$. By parity and the definition of symmetric difference we know $c$ has odd number of neighbors to exactly one of the $U \setminus V$ and $V \setminus U$; It means $c$ has odd number of neighbors in exactly one of the $U$ and $V$ which implies that $c \in F(U) \Delta F(V)$. This proves $F(U \Delta V) \subseteq F(U) \Delta F(V)$.
  2. Suppose $w \in F(U) \Delta F(V)$, we know $w$ has odd number of neighbors in exactly one of the $U$ and $V$ by the definition of $F$ and symmetric difference; It means $w$ has odd number of neighbors in exactly one of the $U \setminus V$ and $V \setminus U$ which implies that $w \in F(U \Delta V)$. This proves $F(U) \Delta F(V) \subseteq F(U \Delta V)$.

  By combining these two together we will have $F(U \Delta V) = F(U) \Delta F(V)$.

• Lemma 2: $F(F(\{x\})) = \{x\}$.
  Prove: It's easy to prove by using the definition of $F$ and using the fact that $k$ is odd which tell us that $deg(x)$ is odd.

Suppose $A = \{ a_i \} _{i=1}^n$. By using lemmas we proved and also applying easy induction on Lemma 1 to get the general form of that (for more than two sets) we will have: $$ F(F(A)) = F(F(\{ a_i \} _{i=1}^n)) = F(F(\Delta_{i=1}^n a_i)) = F(\Delta_{i=1}^n F(a_i)) = \Delta_{i=1}^n F(F(a_i)) = \Delta_{i=1}^n a_i = \{ a_i \} _{i=1}^n = A $$ And done we proved $F(F(A)) = A$. $$\tag*{$\blacksquare$}$$