I am trying to understand group presentations and Cayley graphs, and have a few questions I am confused about.

Let $G=(V,E)$ be a finite $d$-regular graph that is known to be a Cayley graph for the group $\Gamma$ and a symmetric generating set $S=\{s_1,s_2,\dots,s_d\} \subset \Gamma$. Now it is clear that any cycle (or a closed walk) in the graph can be expressed as a word over $S$ that evaluates to the identity in the group $\Gamma$. The converse is also true: any word over $S$ that evaluates to the identity element in $\Gamma$ can be used to construct a cycle in the graph $G$.

Let $R$ be the set of all words over $S$ that evaluate to the identity (in other words, $R$ is the set of all cycles in $G$). The set $R$ is closed under concatenation of words, and is a subgroup of the free group $Free(S)$.

Is it necessarily true that $$\Gamma \cong Free(S)/R$$ that is, is the quotient of the free group by the subgroup of relations formed using cycles in the Cayley graph isomorphic to the group $\Gamma$? Intuitively, it seems reasonable to think so. Almost obvious, (UPDATE: it is obvious!) which brings me to the main question.

Suppose $G=(V,E)$ is again an $n$-vertex $d$-regular graph. But now we do not know if it is a Cayley graph. Choose an arbitrary orientation of each edge and trivially use a larger label set $S=\{s_1,s_2,\dots,s_{|E|}\}$ to associate each oriented edge with a corresponding symbol, and its reverse orientation with an inverse of that symbol. That is, we associate each edge with two (oppositely) oriented (or directed) edges and associate them with a symbol $s$ and $s^{-1}$.

Now again we can consider the free group $Free(S)$ and a subgroup $R$ generated by words over $S$ that correspond to cycles in the graph.

Is $R$ normal? Are there combinatorial conditions on the graph that make $R$ normal?

Suppose $R$ is normal. What can we say about the group $Free(S)/R$? Is there any connection between the graph $G$ and the group $Free(S)/R$?

Suppose, as before, $G$ is a Cayley graph of a group $\Gamma$. Then is the above quotient group isomorphic to $\Gamma$?

I apologize if this question is too broad. I'll try to make it more precise in updates based on feedback. But I'll be happy even with relevant references.

  • $\begingroup$ Thanks. I did realize it soon after posting the question, but left it to serve as a teaser to motivate the actual question after that. Maybe I'll edit it now. $\endgroup$ – BharatRam Aug 2 '17 at 16:57
  • $\begingroup$ If $c\in R$ is any cycle and $e$ any edge then $e^2ce^{-2}$ will not be a cycle, because the target and source of $e$ are different (unless you're allowing loops in your graph). You could define $R$ to be the normal subgroup generated by the cycles. $\endgroup$ – anon Aug 2 '17 at 17:16
  • $\begingroup$ Yes, I had initially written it wrongly having the Cayley picture in mind, but noticed that during my last edit itself where I changed "the subgroup of cycles" to "subgroup generated by cycles". Writing the question itself clears up many confusions :) but the core concept is still unclear. $\endgroup$ – BharatRam Aug 2 '17 at 17:38

Let $R$ be the normal subgroup generated by cycles in $G$. If you take $\Gamma \subset G$ to be a spanning tree, then the generators corresponding to edges in $\Gamma$ will generate all of $\text{Free}(S)/R$. I'm pretty sure that, since there are no cycles in $\Gamma$, there are no extra relations among those generators$^{1}$, which would mean you have $\text{Free}(S)/R \cong F_{|V(G)| - 1}$, the free group on $|V(G)| - 1$ generators (Assuming $G$ is connected).

$^{1}$: If $C$ is the set of cycles, $\langle \cdot \rangle$ denotes normal subgroup generated by a set (so $\langle C \rangle = R$), and $H$ the subgroup of $\text{Free}(S)$ generated by edges in $\Gamma$, I want to say that $H \cap \langle C \rangle = \langle H \cap C \rangle$. I know this isn't true in general, but perhaps in this case it's easy to show?


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.