Let $A=(V, E)$ be a finite simple (no loops or multiple edges) graph. Let $G(A)$ be the following nilpotent group of class 2 and exponent $p$ (an odd prime). $G(A)$ as a set is $span(V)+span(E)$ where $span(X)$ is the elementary abelian group of exponent $p$ generated by the set $X$, and the commutator bracket is given by 1) the subgroup $span(E)$ is the center, 2) if $a,b\in V$ then $[a,b]=e\in E$ if $e$ is the edge connecting $a, b$ in $A$ or $=1$ if there is no edge $(a,b)$ or $(b,a)$. It is clear that every automorphism of the graph $A$ induces an automorphism of the group $G(A)$.

Question 1: Can $Aut(G(A))$ be much bigger than $Aut(A)$?

Update Derek Holt in his comments below showed that $Aut(G(A))$ always contains an elementary abelian normal subgroup of order $p^{|V||E|}$. Here is a more concrete question.

Question 2. Is it true that $Aut(G(A))$ comtains an involution iff $Aut(A)$ contains an involution?

This is related to Automorphism groups of odd order.

The positive answer to the next question would imply the positive answer to Question 2.

Question 3. Let $Q$ be the subgoup of $Aut (G(A))$ consisting of all automorphisms induced by the automorphisms of $A$. Is it true that $Aut(G(A))$ is equal to a semidirect product of $P$ and $Q$?

  • $\begingroup$ Depends on the word much. When the graph is the discrete with $n$ vertices, the numbers are easily computed and the size of $\textit{Aut}(G(A))$ (namely $[n]_p!(p-1)^np^{C(n,2)}$) is larger than the size of $\textit{Aut}(A)$ (which is only $n!$). If you demand nilpotence class exactly two, do the same construction but add one edge. The numbers should be about the same. $\endgroup$ Feb 1, 2020 at 17:04
  • $\begingroup$ ${\rm Aut}(G(A)$ has a normal elementary abelian $p$-subgroup $P$, say, of order $p^{|V||E|}$ consisting of those automorphisms that induce the identity on $G(A)/G(A)'$, which does not occur as a subgroup of ${\rm Aut}(A)$. It would make more sense to compare ${\rm Aut}(A)$ with ${\rm Aut}(G(A)/P$. But the latter is still much bigger in general, because it is a subgroup of ${\rm GL}(|V|,p)$ rather than of ${\rm Sym}(|V|)$. If the graph is empty or complete then we get the whole of ${\rm GL}(|V|,p)$. $\endgroup$
    – Derek Holt
    Feb 1, 2020 at 17:20
  • $\begingroup$ @Keith: I was thinking of generic graphs, highly connected but not full. $\endgroup$
    – user6976
    Feb 1, 2020 at 17:33
  • $\begingroup$ @Derek: Is it true that the number of elements in $P$ is that large? Take the graph with two verticed and one edge (the Heisenberg group of order $p^3$). $\endgroup$
    – user6976
    Feb 1, 2020 at 17:37
  • 3
    $\begingroup$ Would benefit of being tagged in addition graph-theory and finite-groups, maybe also p-groups, and of having a more specific title. $\endgroup$
    – YCor
    Feb 1, 2020 at 18:12

1 Answer 1


I think it's time to write an answer.

Let $G = G(A)$, so $|G| = p^{|V|+|E|}$ with $|G'| = p^{|E|}$ and $G'$ and $G/G'$ are both elementary abelian ($p$-groups with that property are called special $p$-groups, and it is conjectured that almost all finite groups of order up to some bound are special $2$-groups, but that's not relevant to this question.) Note also that by definition $G$ has exponent $p$ and $p$ is odd.

Let $A_G := {\rm Aut}(G)$. As I mentioned in a comment, $A_G$ has a normal elementary abelian subgroup of order $p^{|V|+|E|}$, consisting of those automorphisms that induce the identity on $G/G'$, and hence also on $G'$.

I also mentioned that $A_G$ has another subgroup $Q$, which is cyclic of order $q-1$, and consists of automophisms that induce a scalar linear map on $G/G'$. To define $Q$ precisely, choose any transversal $T$ of $G'$ in $G$. Then a generator of $Q$ maps every element $g \in T$ to $g^{\lambda}$, where $\lambda$ generates the multiplicative group of integers mod $p$, and it maps $g \to g^{\lambda^2}$ for all $g \in G'$. Note that there are $p^{|V| + |E|}$ choices for $T$, and different choices give you conjugates of $Q$ under elements of $P$. Also $QP/P \unlhd A_G/P$. The fact that this really does define an automorphism follows from the fact that it preserves all of the relations in a presentation defining $G$.

So in particular, since $p$ is odd, $A_G$ always has even order, so the answers to Questions 2 and 3 are both no.

You could still ask whether $A_G$ is the semidirect product of $QP$ and the automorphisms of $A_G$ induced from ${\rm Aut}(A)$. The answer to this is again no in general, and it's easy to find small examples in which $A_G$ is bigger, but it is possible that in some sense generically true for random graphs.

This is a difficult topic to investigate computationally, because $A_G$ gets very hard to calculate once $|V|$ is bigger than about 6, and I expect you would need to consider much larger examples in order to get any feel for the generic situation.

But I did do the calculation (in Magma) with a graph with 6 vertices and 6 edges that has trivial automorphism group. The order of $A_G$ turned out to be $2^6 \times 3^{43}$, whereas $PQ| = 2 \times 3^{36}$.

  • $\begingroup$ @DerekbHolt: Thank you! $\endgroup$
    – user6976
    Feb 2, 2020 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.