12
$\begingroup$

Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=\operatorname{Cay}(G, S)$ is a simple undirected connected graph whose vertex set $V\Gamma=G$ and edge set $E\Gamma=\left\{\{g, h\} \mid g^{-1} h \in S \right\}$. It is well known $\Gamma$ is a vertex transitive graph.

A bipartite graph is defined as a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set. Equivalently, a graph $ G = (V, E)$ is bipartite if and only if it does not contain any odd-length cycles.

I want to know under what conditions the Cayley graph is bipartite. Of course, the conclusion is simple when $G$ is a cyclic group, but what about when $G$ is an abelian group, or even a non-abelian one? Are there any conclusions?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
27
$\begingroup$

The Cayley graph is bipartite if and only if there exists a homomorphism $\pi\colon G\to\mathbb Z/2\mathbb Z=\{0,1\}$ such that $\pi(S) \subseteq \{1\}$.

If such a map exists, then the sets $\pi^{-1}(0)$ and $\pi^{-1}(1)$ give a legal coloring. Conversely, if $\operatorname{Cay}(G,S)$ is bipartite, then $$\pi(g)=d_S(g,e_G)\pmod 2$$ is such a map.

Moreover, this condition can easily be checked from a presentation: is every relation of even length?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for your response. Are there any related books or papers that introduce these topics, especially for specific groups? $\endgroup$
    – lunch zheng
    Commented May 4 at 5:46
  • 2
    $\begingroup$ @lunch zheng On which topics? Cayley graphs? I guess any book on geometric group theory will cover this (with more or less examples). I guess my favorites are "Offices Hours with Geometric Group Theorist" and "Topics in geometric group theory" (which I legally binded to promote, being in Geneva). $\endgroup$
    – Corentin B
    Commented May 4 at 14:05
  • $\begingroup$ Thank you, and why is it required here that $\pi$ is a homomorphism? $\endgroup$
    – lunch zheng
    Commented May 5 at 8:55
  • 1
    $\begingroup$ In order to have a proper coloring, we need $\pi(gs)\ne\pi(g)$ hence $\pi(gs)=\pi(g)+1=\pi(g)+\pi(s)$ for all $g\in G$ and $s\in S$. When the target group is $\mathbb Z/2\mathbb Z$, this is equivalent to $\pi$ being an homomorphism. $\endgroup$
    – Corentin B
    Commented May 5 at 9:36
  • $\begingroup$ I get it, by the way, I would like to ask, which book is this theorem from?(The Cayley graph is bipartite) $\endgroup$
    – lunch zheng
    Commented May 14 at 6:06

You must log in to answer this question.

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