# Groups and graphs

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$$?

• 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. Feb 1, 2020 at 17:04
• ${\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)$. Feb 1, 2020 at 17:20
• @Keith: I was thinking of generic graphs, highly connected but not full.
– user6976
Feb 1, 2020 at 17:33
• @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$).
– user6976
Feb 1, 2020 at 17:37
• Would benefit of being tagged in addition graph-theory and finite-groups, maybe also p-groups, and of having a more specific title.
– YCor
Feb 1, 2020 at 18:12

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

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