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.

$\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$ Commented 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
    Commented 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$ Commented 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
    Commented 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$ Commented Jun 9, 2021 at 0:00

0

You must log in to answer this question.

Browse other questions tagged .