7
$\begingroup$

Let $G$ be a finitely generated group and let $\Gamma=Cay(G, S)$ be the Cayley graph of $G$ with respect to some generating set $S$.

If there exists $S$ such that $\Gamma$ is bipartite, then $G$ has an index $2$ subgroup (e.g. generated by all words of even length). Does the converse hold? (I'd guess not, but I don't know generic invariants allowing to show that a group does not admit a bipartite Cayley graph)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If $S=G$, then $\Gamma$ is a clique; hence not bipartite, regardless of whether $G$ has index-$2$ subgroups. $\endgroup$
    – Seva
    Commented Mar 20, 2014 at 11:51
  • 4
    $\begingroup$ If $H$ has index $2$ in $G$, then just take $S$ to be any (finite) generating set of $G$ none of whose elements lie in $H$. $\endgroup$
    – Derek Holt
    Commented Mar 20, 2014 at 11:56

1 Answer 1

Reset to default
8
$\begingroup$

Is bipartite or admits bipartite? To the first question the answer is obviously "no", to the second, obviously "yes". Let $H\subset G$ be an index $2$ subgroup; take generators $h_1,h_2,\ldots$ for $H$ and one more generator $g\notin H$. In this generating set, the Cayley graph is not bipartite (with a few possible exceptions). However, if you switch to $g, h_1g, h_2g,\ldots$, this is also a generating set and all generators have "odd degree", so the graph is obviously bipartite.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sorry, how come all the elements $g, h_1g, h_2g, \ldots$ have 'odd degree'. Could you elaborate? $\endgroup$
    – vidyarthi
    Commented May 8, 2022 at 17:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .