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$?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityYes, 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.
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.
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$}$$