1
$\begingroup$

Notation. Consider the group $\Gamma=\mathbb{Z}_2^n$. I will denote the group operation aditively and by $\epsilon_i=(0,\dots,0,1,0,\dots,0)$ I denote the canonical generators. Let's define also $\epsilon_0:=0$ and $\epsilon_{n+1}:=(1,1,\dots,1)=\epsilon_1+\cdots+\epsilon_n$. I will denote by $\tau_i\in C(\Gamma)\simeq \mathbb{C}\Gamma$ the character corresponding to $\epsilon_i$. That is $\tau_i(\alpha)=(-1)^{\alpha_i}$ for $\alpha=(\alpha_1,\dots,\alpha_n)\in\Gamma$. I will also denote $\tau_0=1_{C(\Gamma)}$ and $\tau_{n+1}=\tau_1\cdots\tau_n$.

Halved hypercube graph can be defined as the Cayley graph corresponding to $\Gamma$ with respect to the generating set $S=\{\epsilon_i\}_{1\le i\le n}\cup\{\epsilon_i+\epsilon_j\}_{1\le i<j\le n}$. Or maybe a bit nicer: $S=\{\epsilon_i+\epsilon_j\}_{0\le i\le j\le n}$. In general, the set of vertices in a given distance $d$ from the vertex $0$ is given by $S_d=\{\epsilon_{i_1}+\cdots+\epsilon_{i_{2d}}\mid 0\le i_1<i_2\cdots< i_{2d}\le n\}$. Since it is a Cayley graph of an abelian group $\Gamma$, the eigenvectors of the adjacency matrix are exactly the characters of $\Gamma$. One can easily compute the spectrum, which is not that important, but the eigenspaces look as follows $V_d=\mathop{\rm span}\{\tau_{i_1}\cdots\tau_{i_d}\mid 1\le i_1<\cdots<i_d\le n+1\}$.

Folded hypercube graph can be defined as the Cayley graph corresponding to $\Gamma$ with respect to the generating set $S=\{\epsilon_1,\dots,\epsilon_n,\epsilon_{n+1}\}$. The set of vertices in distance $d$ from $0$ is given by $S_d=\{\epsilon_{i_1}+\cdots+\epsilon_{i_d}\mid 1\le i_1<\cdots<i_d\le n+1\}$ and the eigenspaces by $V_d=\mathop{\rm span}\{\tau_{i_1}\cdots\tau_{i_{2d}}\mid 0\le i_1<\cdots<i_{2d}\le n\}$.

Observation. The two graphs are dual to each other in the sense that the set $S_d\subset\Gamma$ for one exactly matches the eigenspace $V_d\subset\mathbb{C}\Gamma$ for the other.

Questions. Does this duality have any deeper meaning? Is this a more general phenomenon? I mean, can one define a dual graph for any, let's say, Cayley graph of an abelian group such that taking the dual twice, one arives at the original one? If so, I would appreciate some reference.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ \What, you’re seeing is an instance of duality on the association scheme of an abelian group. A more helpful comment is that the case you have ($\mathbb{Z}_2^n$) can be described by the Hadamard transform from coding theory. $\endgroup$
    – Chris Godsil
    Jun 2, 2021 at 13:53
  • $\begingroup$ @ChrisGodsil Is it clear that if I start with the association scheme of a distance-regular Cayley graph, then the dual association scheme will again correspond to a (distance-regular) graph? $\endgroup$
    – Daniel
    Jun 4, 2021 at 8:14
  • $\begingroup$ No, you are only guaranteed a dual graph if your group is abelian, and even then, if your graph is distance regular, the dual need not be. (Although examples are not easy to find.) $\endgroup$
    – Chris Godsil
    Jun 5, 2021 at 15:11
  • $\begingroup$ @ChrisGodsil I do not fully understand. Given a graph, I may define its association scheme by taking the corresponding distance-$i$-graphs. To do that, the graph must be distance regular – that's an axiom of association schemes. If, in particular, I consider a Cayley graph of an abelian group, I can always construct the dual association scheme. My question is, whether this association scheme again corresponds to a graph. If so, then the graph already must be distance regular, right? $\endgroup$
    – Daniel
    Jun 7, 2021 at 7:16
  • 1
    $\begingroup$ (Fixing my previous comment.) The classes in an association scheme need not be defined in terms of graph distances; there does not need to be any distance regular graph present. $\endgroup$
    – Chris Godsil
    Jun 9, 2021 at 0:00

0

Reset to default

Your Answer

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