|
10
|
|
edited Mar 1 2012 at 18:52 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets that generate the group ($\textit{i.e.}$ such that the words in $S \cup S^{-1}$ give the full group). Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are isomorphic, given that $S$ and $T$ are "mag".
Apologies in advance if the answer is well-known...
PS: Here by Cayley graph of $G$ w.r.t. $S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.
PPS: given minimality of $S$ and finiteness of the group, $S$ will usually be anti-symetric.
Here are examples. Take $G = \mathbb{Z}$ and $ H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$ there is not much a choice for the generating set (and it's going to be symmetric); H$, picking $ \lbrace a,b \rbrace$ the resulting Cayley graph is going to be infinite unoriented path ("two-way" infinite street). For $G$ however, G$, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. Thus In either case, the resulting (oriented) Cayley graph is going to be a infinite unorientd path ("one-way" infinite street).
There might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.
|
|
|
|
|
9
|
|
edited Feb 27 2012 at 8:25 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that generate the group ($\textit{a priori}$) subsemigroup generated by $\textit{i.e.}$ such that the words in $S \cup S^{-1}$ is give the full groupgroup). Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are isomorphic, given that $S$ and $T$ are "mag".
Apologies in advance if the answer is well-known...
PS: Here by Cayley graph of $G$ w.r.t. $S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.
PPS: the assumption that the semigroup generated by $S \cup S^{-1}$ is the full group is superfluous given minimality of $S$ and finiteness of the group. But if the groupis infinite, it makes a difference$S$ will usually be anti-symetric.
Here are examples. Take $G = \mathbb{Z}$ and $ H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$ there is not much a choice for the generating set (and it's going to be symmetric); the resulting Cayley graph is going to be "two-way" lineinfinite unoriented path ("two-way" infinite street). For $G$ however, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. Thus the resulting (oriented) Cayley graph is going to be a "one-way" lineinfinite unorientd path ("one-way" infinite street).
So there
There might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.
|
|
|
|
|
8
|
|
edited Feb 26 2012 at 17:48 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that the (\emph{a priori}$\textit{a priori}$) subsemigroup generated by $S \cup S^{-1}$ is the full group. Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are isomorphic, given that $S$ and $T$ are "mag".
PS: Here by Cayley graph of $G$ w.r.t. $S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.
PPS: the assumption that the semigroup generated by $S \cup S^{-1}$ generates is the full group is superfluous (given minimality ) if and finiteness of the groupis finite. But if the group is infinite, it makes a difference. Take $G = \mathbb{Z}$ and $ H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$ there is not much a choice for the generating set (and it's going to be symmetric); the resulting Cayley graph is going to be "two-way" line. For $G$ however, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. Thus the resulting (oriented) Cayley graph is going to be a "one-way" line.
So there might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.
|
|
|
|
7
|
|
edited Feb 26 2012 at 17:40 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that the (\emph{a priori}) subsemigroup generated by $S \cup S^{-1}$ generates is the full group. Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are isomorphic, given that $S$ and $T$ are "mag".
PS: Here by Cayley graph of $G$ w.r.t. $S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.
PPS: the assumption that $S \cup S^{-1}$ generates the group is superfluous (given minimality) if the group is finite. But if the group is infinite, it makes a difference. Take $G = \mathbb{Z}$ and $ H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$ there is not much a choice for the generating set (and it's going to be symmetric); the resulting Cayley graph is going to be "two-way" line. For $G$ however, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. Thus the resulting (oriented) Cayley graph is going to be a "one-way" line.
So there might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.
|
|
|
|
|
6
|
|
edited Feb 26 2012 at 17:31 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that $S \cup S^{-1}$ generates the group. Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are identicalisomorphic, given that $S$ and $T$ are "mag".
PS: Here by Cayley graph of $G$ w.r.t. $S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.
PPS: the assumption that $S \cup S^{-1}$ generates the group is superfluous (given minimality) if the group is finite. But if the group is infinite, it makes a difference. Take $G = \mathbb{Z}$ and $ H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$ there is not much a choice for the generating set (and it's going to be symmetric); the resulting Cayley graph is going to be "two-way" line. For $G$ however, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. Thus the resulting (oriented) Cayley graph is going to be a "one-way" line.
So there might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.
|
|
|
|
|
5
|
|
edited Feb 26 2012 at 10:54 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that $S \cup S^{-1}$ generates the group. Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are identical, given that $S$ and $T$ are "mag".
PS: Here by Cayley graph of $G$ w.r.t. $S$ S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.
PPS: the assumption that $S \cup S^{-1}$ generates the group is superfluous (given minimality) if the group is finite. But if the group is infinite, it makes a difference. Take $G = \mathbb{Z}$ and $ H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$ there is not much a choice for the generating set (and it's going to be symmetric); the resulting Cayley graph is going to be "two-way" line. For $G$ however, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. Thus the resulting (oriented) Cayley graph is going to be a "one-way" line.
So there might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.
|
|
|
|
|
4
|
|
edited Feb 25 2012 at 3:26 |
Non-isomorphic groups with distinct the same oriented Cayley graphs graph
|
|
|
|
|
3
|
|
edited Feb 24 2012 at 22:03 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that $S \cup S^{-1}$ generates the group. Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are identical, given that $S$ and $T$ are "mag".
PS: Here by Cayley graph of $G$ w.r.t. $S$ I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.
|
|
|
|
|
2
|
|
edited Feb 24 2012 at 20:02 |
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that $S \cup S^{-1}$ generates the group. Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are identical, given that $S$ and $T$ are "mag".
Apologies in advance if
PS: Here by Cayley graph of $G$ w.r.t. $S$ I mean the examples graph whose vertices are well-known...$G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.)
|
|
|
|
|
1
|
|
asked Feb 23 2012 at 19:44 |
Non-isomorphic groups with distinct oriented Cayley graphs
There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following
$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets such that $S \cup S^{-1}$ generates the group. Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are identical, given that $S$ and $T$ are "mag".
Apologies in advance if the examples are well-known...
|
|
|
