Return to Question

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); the resulting Cayley graph is going to be infinite 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 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.

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$, picking $ \lbrace a,b \rbrace$ the resulting Cayley graph is going to be infinite unoriented path ("two-way" infinite street). For $G$, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. 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.

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 ($\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}$ is the full group is superfluous given minimality and finiteness of the group. 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.

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); the resulting Cayley graph is going to be infinite 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 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.

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}$ 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.

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 ($\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}$ is the full group is superfluous given minimality and finiteness of the group. 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.