4
$\begingroup$

The same question with groups instead of monoids is answered negatively, see here. From this question, it is true that any finite group is the automorphism group of some monoid.

Moreover, what happens if we require the monoid to be commutative?

(I believe that my question with "semigroup" instead of "monoid" has the same answer – removing or adding the identity element shouldn't change so much).

$\endgroup$
  • $\begingroup$ This might be related: mathoverflow.net/questions/37356/… (in view of the second question I cited). $\endgroup$ – Alphonse May 13 '18 at 15:06
  • 6
    $\begingroup$ Just reading through your links, one finds: (1) Every group is the automorphism group of some (wlog. directed) graph; (2) For every directed graph, we find a semigroup with the same automorphism group; (3) adding or removing the identity element does not change the automorphism group. -- Am I misisng something? $\endgroup$ – Hagen von Eitzen May 13 '18 at 15:18
  • $\begingroup$ @HagenvonEitzen : I see, but there might be an easier/more direct proof, though. $\endgroup$ – Alphonse May 13 '18 at 15:21
  • $\begingroup$ @HagenvonEitzen : I also would like to know if we can require the monoid to be commutative, i.e. for any group $G$, there is a commutative monoid $M$ with $Aut(M) \cong G$. $\endgroup$ – Alphonse May 13 '18 at 15:35
1
$\begingroup$

Let $G$ be an arbitrary group. We construct an edge-colured graph $(V,E,C,\Gamma)$ having $G$ as automorphism group: As set of vertices, we take $V=G$, as set of edges, we take $E=\{\,g\to h: g,h\in G, g\ne h\,\}$ (i.e., we are dealing with thge complete directed graph on $G$). As set of colours, we take $C=G\setminus\{1\}$, and let the colouring $\Gamma\colon E\to C$ be given as $\Gamma(g\to h)=hg^{-1}$.

Claim. Let $G$ ba any group and $(V,E,C,\Gamma)$ as described above. Then $\operatorname{Aut}(V,E,C,\Gamma)\cong G$.

Proof. If $a\in G$, then $\phi_a\colon V\to V$, $g\mapsto ga$ induces an automorphism. Indeed, if $g\to h$ is an edge then so is $ga\to ha$, and we have $\Gamma(ga\to ha)=ha(ga)^{-1}=hg^{-1}=\Gamma(g\to h)$. As $\phi_a(1)=a$, we see that $a\mapsto \phi_a$ is a monomorphism $G\to \operatorname{Aut}(V,E,C,\Gamma)$. On the other hand, let $\phi$ be an arbitrary automorphism of $(V,E,C,\Gamma)$ and let $a=\phi(1)$. Then $\phi=\phi_a$ because for any $g\ne 1$, the edge $a\to \phi(g)$ must have the same colour as $1\to g$, hence $\phi(g)a^{-1}=g$, $\phi(g)=ga$. $\square$


Let $(V,E,C,\Gamma)$ be an edge-coloured directed graph, where wlog. $C$ is an ordinal. We define an (un-coloured) directed graph $(V',E')$ as follows. Let $V'$ consist of

  • a vertex $v$ for each $v\in V$
  • a new vertex $\hat v$ for each $v\in V$
  • a new vertex $(\beta,v, w)$ for each edge $v\to w$ in $E$ and $\beta\le \Gamma(v\to w)$

Let $E'$ consist of

  • an edge $v\to \hat v$ for each $v\in V$
  • an edge $v\to (0,v,w)$ for each edge $v\to w$ in $E$
  • an edge $(\Gamma(v\to w),v,w)\to w$ for each edge $v\to w$ in $E$
  • an edge $(\beta,v,w)\to (\gamma,v,w)$ whenever $0\le \beta<\gamma\le \Gamma(v\to w)$

Claim. Let $(V',E')$ be obtained as described from $(V,E,C,\Gamma)$. we have $\operatorname{Aut}(V'E')\cong\operatorname{Aut}(V,E,C,\Gamma)$.

Proof. Given an automorphism $\phi$ of $(V,E,C,\Gamma)$, we can readily find a corresponding automorphism of $(V',E')$ by mapping vertices $$\begin{align}v&\mapsto \phi(v),\\ \hat v&\mapsto \widehat{\phi(v)},\\ (\beta,v,w)&\mapsto (\beta,\phi(v),\phi(w)).\end{align}$$ This gives us a monomorphism $\operatorname{Aut}(V,E,C,\Gamma)\to \operatorname{Aut}(V'E')$. We need to show that it is onto. Vertices of the second type ("$\hat v$") are characterized by the fact that they have no successors. Vertices of the first type ("$v$") are characterized by the fact that they have a successor of the first type. Thus also vertices of the third type are characterized. An automorphism $\phi$ of $(V',E')$ must respect types. Moreover, vertices of the third type with ordinal $0$ are characterized by being of third type and having a type one predecessor, so this must also be respected by an automorphism. Assume $\phi((0,v,w))=(0,a,b)$ where $v\to w$ is an edge in $E$ of colur $c$. Then $\phi(v)=a$ by looking at the unique predecessors and $\phi(\hat v)=\hat a$ by their type 1 successors. I claim that $\phi((\beta,v,w))=(\beta,a,b)$ for all $\beta\le c$. Indeed, if $\beta>0$ and the claim holds for all smaller ordinals, then $\phi((\beta,v,w))$ is determined among all type 3 vertices by the fact that precisely all $(\gamma,a,b)$ with $\gamma<\beta$ are predecessors. After that, note that $w$ is the unique successor of $(c,v,w)$, hence $(c,a,b)$ must have a sucessor of second type; this must be $b$ and therefore $\Gamma(a\to b)=c$ and $\phi(w)=b$. We conclude that $\phi$ induces a permutation of $V$ and is uniquely determined by that permutation, and if $v\to w$ is an edge in $E$ then $\phi(v)\to \phi(w)$ is also an edge and is of the same colour. In other words, our monomorphism $\operatorname{Aut}(V,E,C,\Gamma)\to \operatorname{Aut}(V'E')$ is in fact an isomorphism. $\square$


Next, $(V,E)$ be a directed graph. We define an undirected graph $(V',E')$ as follows.

Let $V'=V\cup (E\times\{1,2,3,4\}$, i.e., $V'$ consists of

  • a vertex $v$ for each $v\in V$
  • new vertices $(v,w)_1, (v,w)_2, (v,w)_3, (v,w)_4$ for each edge $v\to w\in E$

and let $E'$ consist of

  • edges $v\leftrightarrow (v,w)_1$,
  • $v\leftrightarrow (v,w)_2$,
  • $v\leftrightarrow (v,w)_3$,
  • $(v,w)_1\leftrightarrow (v,w)_2$,
  • $(v,w)_2\leftrightarrow (v,w)_3$,
  • $(v,w)_2\leftrightarrow (v,w)_4$,
  • $(v,w)_3\leftrightarrow w$ for each edge $v\to w$ in E$

Claim. With $(V',E')$ obtained from $(V,E)$, we have $\operatorname{Aut}(V,E)\cong \operatorname{Aut}(V',E')$.

Proof. As before, from an automorphism $\phi$ of $(V,E)$, we readily obtain an automoprhism of $(V','E')$ that maps $v\mapsto \phi(v)$ and $(v,w)_i\mapsto (\phi(v),\phi(w))_i$., thereby obtaining a monomoprhism $\operatorname{Aut}(V,E)\to\operatorname{Aut}(V',E')$.

Now let $\phi$ be any automophism of $(V',E')$. Observe that vertices of the form $(v,w)_1$ are precisely those that are of degree $2$ and with an edge between their neighbours. These two neighbours have precisely one other common neighbour, namely the corrsponding $(v,w)_3$. Exactly one of these common neighbours, namely $(v,w)_2$, has a neigbour of degree $1$, which is $(v,w)_4$; the other common neighbour must be $v$. And the only neighbour of $(v,w)_3$ not yet mentioned is $w$. We conclude that $\phi$ must map $(v,w)_1$ to some $(a,b)_1$ and that then $\phi(v)=a$, $\phi(w)=b$, $\phi((v,w)_i)=(a,b)_i$. In particular $\phi$ induces a permutation of $V\subset V'$ and such that $(V,E)$ has an edge $\phi(v)\to\phi(w)$ whenever $v\to w$ is an edge. In other words, our monomorphism $\operatorname{Aut}(V,E)\to\operatorname{Aut}(V',E')$ is an isomorphism. $\square$


Finally, given an undirected graph $(V,E)$, we construct a commutative semigroup with the same automorphism group: Let $S=V\cup E\cup\{0\}$ and declare

  • $vv=v$ if $v\in V$
  • $ve=ev=e$ if $v\in V$ is an end vertex of edge $e\in E$
  • $xy=0$ otherwise.

Any automorphism of the graph gives rise to an automorphism of $S$. On the other hand, any automorphism of $S$ must respect vertices (idempotent elements) and edges (other non-zero elements)products) and vertex-edge incidence (vertex and edge with non-zero product)

(This essentially repeats the construction given in the accepted answer to one of the referenced similar questions).

This shows the final

Claim. Let $(V,E)$ be an undirected graph. Then there exists a commutative monoid $S$ such that $\operatorname{Aut}(V,E)\cong\operatorname{Aut}(S)$. $\square$


Combining all of the above, we see that for every (finite or inifnite) group $G$, there exists a commutative monoid $S$ such that $$\operatorname{Aut}(S)\cong G. $$

$\endgroup$
  • $\begingroup$ Thank you! I need to read this, but why does it follow that any group is the automorphism group of some commutative monoid? $\endgroup$ – Alphonse May 13 '18 at 21:25
  • $\begingroup$ @Alphonse because $S$ is clearly commutative. $\endgroup$ – Hagen von Eitzen May 14 '18 at 13:43
  • $\begingroup$ @Alphonse I tried to edit to be more explicit $\endgroup$ – Hagen von Eitzen May 14 '18 at 15:45

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.