Timeline for When can the Cayley graph of the symmetries of an object have those symmetries?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2016 at 15:21 | vote | accept | Joseph O'Rourke | ||
| Jul 18, 2016 at 13:12 | answer | added | Frieder Ladisch | timeline score: 3 | |
| Jul 18, 2016 at 13:01 | answer | added | ARG | timeline score: 2 | |
| Jul 18, 2016 at 12:59 | comment | added | Joseph O'Rourke | Thanks for the fascinating discussion, and apologies for the flawed question. I just thought it would be neat to represent the symmetries of an object by a graph with the same symmetries. Because my motivation was from geometry, indeed I was interested in geometric embeddings. | |
| Jul 18, 2016 at 12:54 | answer | added | user95205 | timeline score: 1 | |
| Jul 18, 2016 at 12:51 | comment | added | ARG | @StefanKohl: I misread the question. As I read it, there was no constraint that the Cayley graph must be embedded into $\mathbb{R}^n$. It is perfectly ok to speak of the symmetries of a graph without embedding it geometrically. In the "abstract" setting, Nick Gill just posted a link to a complete answer (i.e. when is are the "abstract" automorphisms exactly $G$). I would guess the geometrical question is harder. The "simple" negatives (with complete graphs, without dimension bound) persist however. Embed $G$ in $\mathbb{R}^G$ by sending each vertex to a "Dirac mass". | |
| Jul 18, 2016 at 12:47 | comment | added | Nick Gill | In light of my earlier comment -- that you can ignore the embedding for large enough $m$ -- then you could just consider the question of finding Graphical regular representations - i.e. Cayley graphs of a group $G$ such that $Aut(\Gamma(G,S))=G$. There's a bunch of literature on this, and you might find the answer of Chris Godsil to this question interesting: math.stackexchange.com/questions/1098115/… | |
| Jul 18, 2016 at 12:44 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Clarity.
|
| Jul 18, 2016 at 12:37 | comment | added | Nick Gill | @StefanKohl, you're quite right, that's exactly what I was thinking. I agree with you about the negative examples. | |
| Jul 18, 2016 at 12:35 | comment | added | Stefan Kohl♦ | @NickGill: You probably mean to obtain positive examples. -- What I meant is that negative examples you won't get in this way. | |
| Jul 18, 2016 at 12:31 | comment | added | Nick Gill | @StefanKohl, On the other hand it seems to me that once $m$ gets big enough, you should be able to embed any graph into $\mathbb{R}^m$ so that the aut gp of the embedding is the same as the graph (put the vertices on orthogonal unit vectors I guess), so one should be able to start by just considering the automorphism group of the graph, as Antoine suggests. | |
| Jul 18, 2016 at 12:28 | comment | added | Stefan Kohl♦ | @Antoine: The embedding of a graph into $\mathbb{R}^n$ can have a symmetry group which is different from the automorphism group of the graph. -- For example, a complete graph has embeddings into $\mathbb{R}^n$ whose symmetry groups are much smaller than ${\rm S}_n$, or even trivial. | |
| Jul 18, 2016 at 11:58 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Responding to Ladisch comment.
|
| Jul 18, 2016 at 11:57 | comment | added | Joseph O'Rourke | @FriederLadisch: Good point. Altered accordingly. | |
| Jul 18, 2016 at 11:20 | comment | added | Frieder Ladisch | I do not understand why you think of the nodes as colored (labeled by generators)? Isn't the usual definition that the arcs are labeled by generators, and the nodes simply correspond to the group elements? And I observe that your example digraph has reflection symmetries only if you forget about the directions of the $r$-arcs. | |
| Jul 18, 2016 at 10:30 | comment | added | Joseph O'Rourke | @GerhardPaseman @ Antoine: Thanks for your excellent points and observations. | |
| Jul 18, 2016 at 10:14 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 28 characters in body
|
| Jul 18, 2016 at 9:18 | comment | added | ARG | Also, for Abelian groups, I believe there is a paper by Clara Loeh which is relevant for your question. | |
| Jul 18, 2016 at 9:15 | comment | added | ARG | for negative examples (as @GerhardPaseman implicitly mentioned): take the genertaing set to be the whole group; on gets a complete graph with symmetries $S_{|G|}$ which is (unless $|G| \leq 2$) different from $G$. In general, $G$ is always a subgroup of the automorphism group of its Cayley graphs (by acting of the left; if edges are defined by right-multiplication). Since more edges will allow for more symmetries, you should (for positive examples) always try to pick a generating set which is minimal (w.r.t. inclusion). Typical positive examples are cyclic and dihedral groups. | |
| Jul 18, 2016 at 1:43 | comment | added | Gerhard Paseman | As I understand it, there is no Cayley graph of a group G. There is one of a group G with a given generating set S $\subseteq$ G. (Thus I think the answer you want highly depends on S.) There may be a default case where if no generating set is specified, then G is taken also as the generating set, but then I think the graph looks less interesting. Gerhard "Not Always Into Complete Graphs" Paseman, 2016.07.17. | |
| Jul 18, 2016 at 1:25 | history | asked | Joseph O'Rourke | CC BY-SA 3.0 |