11
$\begingroup$

Since it is not the case that every group is the automorphism group of a group (see Is every group the automorphism group of a group?), it is natural to ask: what are some examples of classes $\mathcal{C}$ of structures such that for each finite group $G$, there exists a structure $C$ of class $\mathcal{C}$ such that $\text{Aut}(C) \cong G$?

As discussed in Peter Cameron's Automorphisms of graphs, a class $\mathcal{C}$ of structures is said to be universal if every finite group is the automorphism group of a structure in $\mathcal{C}$. As indicated in this article, the following classes of structures are universal:

$\bullet$ The class of graphs (Frucht's theorem);

$\bullet$ The class of trivalent graphs;

$\bullet$ The class of graphs of valency $k$ for fixed $k > 2$;

$\bullet$ The class of bipartite graphs;

$\bullet$ The class of strongly regular graphs;

$\bullet$ The class of Hamiltonian graphs;

$\bullet$ The class of $k$-connected graphs for $k \in \mathbb{N}$;

$\bullet$ The class of $k$-chromatic graphs for $k > 1$;

$\bullet$ The class of finite distributive lattices;

$\bullet$ Switching classes of graphs;

$\bullet$ The class of projective planes;

$\bullet$ The class of Steiner triple systems; and

$\bullet$ The class of balanced incomplete block designs.

It is also known that:

$\bullet$ The class of matroids is universal, as shown in the article On the automorphism group of a matroid;

$\bullet$ The class of finite posets is universal, as shown in the article Automorphism groups of finite posets; and

$\bullet$ The class of complete, connected, locally connected metric spaces of any fixed positive dimension is universal, as discussed in the following link: Automorphism group of a topological space;

$\bullet$ The class of directed acyclic graphs is universal, as discussed in the following link: Can any finite group be realized as the automorphism group of a directed acyclic graph?; and

$\bullet$ The class of finite orthomodular lattices is universal, as proven in the article Every finite group is the automorphism group of some finite orthomodular lattice.

Observe that most of the universal classes given above are classes of combinatorial/discrete structures as opposed to algebraic structures defined in terms of binary operations such as monoids and rings, or geometric structures such as manifolds. It is natural to ask:

(1) What are some other interesting examples of universal classes of structures?

(2) Are there any known examples of universal classes of 'algebraic' structures, i.e. structures endowed with at least one binary operation satisfying certain axioms? Is the class of rings universal? Is the class of monoids universal? Is the class of semigroups universal?

(3) Are there any known examples of universal classes of 'geometric' structures, e.g., structures such as smooth manifolds?

(4) What are some interesting examples of classes of structures which are known to be non-universal? As shown by Polya, one such example is the class of trees. It is also known that the class of planar graphs is not universal. Also, it is known that any minor-closed class of graphs is not universal.

$\endgroup$
  • 3
    $\begingroup$ I like the research you have done on the references, +1 from me! $\endgroup$ – Nicky Hekster Mar 25 '16 at 20:35
4
+50
$\begingroup$

The classes of monoids and semigroups are universal.

Adjoining an identity to a semigroup doesn't change the automorphism group, so it's enough to prove this for semigroups, for which I'll use the fact that the class of directed (acyclic) graphs is universal.

Let $G$ be a directed graph with vertex and edge sets $V$ and $E$. Define a semigroup $S=V\cup E\cup\{0\}$ with all products equal to $0$ except that, for $v\in V$ and $e\in E$, $v^2=v$, $ve=e$ if $v$ is the initial vertex of $e$, and $ev=e$ if $v$ is the terminal vertex of $e$.

Then it is easy to see that the automorphism group of $S$ is the same as that of $G$.

In fact, since universality of directed graphs only requires finite graphs, even the classes of finite monoids and semigroups are universal.

$\endgroup$
  • $\begingroup$ Do you know if the category of commutative semigroups is "universal" in the above sense? This is related to my question here. $\endgroup$ – Alphonse May 13 '18 at 17:54
  • 1
    $\begingroup$ @Alphonse I think the answer of Hagen von Eitzen to your linked question answers that, as the semigroup he constructs at the end of his answer is commutative. $\endgroup$ – Jeremy Rickard May 14 '18 at 8:40

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.