0
$\begingroup$

Some facts are-

  1. Group can be represented by a graph.

  2. Group Isomorphism $\leq_p$ Graph Isomorphism.

Under this context, my questions is-

  1. Can a triangle free graph represent a group?

Edit: My motivation is to see the interaction between group isomorphism and graph isomorphism,so please consider groups that can be represented by simple graphs but not trees as tree isomorphism can be solved in log time.

In general, consider hard instances of groups for group isomorphism which are represented by graphs that are also hard graph isomorphism instances.

$\endgroup$
  • $\begingroup$ When you say "groups can be represented by a graph" do you mean the Cayley graph ? $\endgroup$ – Captain Lama Apr 27 '16 at 16:46
  • $\begingroup$ @CaptainLama yes, caley graphs are directed but even if you don't keep the direction of caley graph , they still represent a group. $\endgroup$ – Jim Apr 27 '16 at 16:55
  • 2
    $\begingroup$ Then free groups are "represented" by trees. $\endgroup$ – Captain Lama Apr 27 '16 at 16:56
  • 1
    $\begingroup$ Like... the Cayley graph for a cyclic group with $n \neq 3$ elements? $\endgroup$ – pjs36 Apr 27 '16 at 17:21
  • 2
    $\begingroup$ At any rate, if you just wants lots of examples of (gorgeous) Cayley graphs, check out weddslist. You can spot a few different Cayley graphs for a variety of groups. $\endgroup$ – pjs36 Apr 27 '16 at 17:27
1
$\begingroup$

The thing is that the Cayley graph is not canonical : for a given group $G$, each choice of a generating set will give a different Cayley graph.

And every group with at least $3$ elements has a Cayley graph with triangles : if $x\neq y$ in $G$, put $x$, $y$ and $xy^{-1}$ in the generating set, and this will give you a triangle in the Cayley graph.

On the other hand, unless your generating set has elements of order $3$, you can always remove the triangles by changing the generating set. Indeed, if there is a triangle, then by homogeneity you canfind one with one of the vertices labeled by the neutral element. Then (assuming the generating set $S$ is symmetric) the other two vertices are labeled with $x,y\in S$ and the edges are labeled with $x$, $y$ and $z\in S$. The fact that it's a triangle then means that $z=yx^{-1}$ or $z=yx^{-1}$. Then analysing all cases ($z=x^{\pm 1}$, $z=y^{\pm 1}$, $z\neq x^{\pm 1},y^{\pm 1}$) shows that you can remove one of those generators, thus removing the triangle.

$\endgroup$
  • $\begingroup$ I think your last statement is correct, but it is not obvious and a proof requires some work. For example, it is not true if you replace $3$ by $4$. If you take an abelian group of rank at least 2, then, for any generating set, the corresponding Cayley graph will have $4$-cycles, (even if the group has no element of order $4$). $\endgroup$ – verret Apr 27 '16 at 20:02
  • $\begingroup$ You're right, I added a short proof. $\endgroup$ – Captain Lama Apr 27 '16 at 20:15
  • $\begingroup$ That proof is incorrect. For example, on the surface, that proofs work for 4 as well, but the conclusion is wrong in this case. The problem is that the 3- or 4-cycle might have repeated elements. In your notation, we might have $x=z$ so that removing $z$ removes $x$ and we might no longer have a generating set. In the 3-cycle case, that can actually be avoided, with some care... $\endgroup$ – verret Apr 27 '16 at 20:22
  • $\begingroup$ Ah, that's not what I would call a triangle, then. I guess it's a matter of definitions. $\endgroup$ – Captain Lama Apr 27 '16 at 20:23
  • 1
    $\begingroup$ Yes, you can always find a Cayley graph with triangles for your group if it has at least $3$ elements. $\endgroup$ – Captain Lama May 18 '16 at 21:39

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.