2
$\begingroup$

I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how to interpret it. It runs as follows:

Let $\Gamma$ be a group and $S$ be a subset of $\Gamma$ not including the identity element. Suppose that the inverse of every element in $S$ also belongs to $S$. The Cayley graph of $\Gamma$ with respect to $S$ is the graph $CG(\Gamma, S)$ with vertex set $\Gamma$ in which two vertices $x$ and $y$ are adjacent iff $xy^{-1}\in S$.

Okay. I follow so far.

Recall that the n-cube is the graph whose vertex set is the set of all n-tuples of 0s and 1s, where two n-tuples are adjacent if they differ in precisely one coordinate.

Makes sense.

Show that the n-cube is a Cayley graph.

What does it mean to talk about "$xy$" when $x$ and $y$ are n-tuples? What is the inverse of an n-tuple?

Someone I asked about the problem suggested that I treat $\Gamma$ here as the additive group $({\mathbb Z}/2{\mathbb Z})^n$, and so take $xy^{-1}$ to mean elementwise subtraction of $y$ from $x$, mod 2. But then it seems like $(0, 0, ..., 0)\in\Gamma$ and, since it's the identity element, every vertex will have an edge connecting to it, and that isn't what the n-cube looks like. Googling, I also see that there is an interpretation of tuples as nested sets, but then I don't see how the product of two nested sets would ever be in S, since it will have a different cardinality from either of the original tuples. Interpreting the tuples as vectors can't work either since then $xy^{-1}$ will have different dimensions than either of the original tuples.

What is this question asking?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ If every vertex has an edge connecting to (0,0,...,0), then every non-identity element is in S. $\hspace{1.01 in}$ $\endgroup$ – user12859 Apr 13 '14 at 3:30
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Apr 13 '14 at 8:23
3
$\begingroup$

The question is asking you to find a suitable group $\Gamma$ and a subset $S$, so that $CG(\Gamma,S)$ is the n-cube.

Since by definition of $CG$, the nodes are the elements of $\Gamma$, you don't have a choice here, leaving the group operation and $S$.

$xy$ and the inverse of $y$ are then understood with respect to the group operation you choose.

Also be aware that the identity element being in $\Gamma$ does not imply that all other vertices are connected with it, since the edges are determined by $S$, not $\Gamma$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Okay, so any $\Gamma$ will work? In particular, I could, say, call $\Gamma$ the set of all n-bit integers, define the group operation to be XOR, and let $S$ be all of the powers of two, from 0 to $n$? And provide a mapping from n-element tuples to n-bit integers to show that they're equivalent? $\endgroup$ – Patrick Collins Apr 13 '14 at 19:27
  • $\begingroup$ @PatrickCollins That should work. $\endgroup$ – FrankW Apr 13 '14 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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