2
$\begingroup$

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

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ A simpler (in my opinion) way to see that $M^2 = I$: notice that $M = M_1 + \cdots + M_k$ where $M_i$ sends a vertex om the hypercube to the adjacent vertex in the $e_i$-direction. Then modulo $2$ we have $M^2 = M_1^2 + \cdots + M_k^2 = I$ because it is easy to see that $M_i^2 = I$. $\endgroup$
    – Random
    Apr 22, 2023 at 15:13
4
$\begingroup$
  • 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$}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.