# Can every involution of a symmetric directed graph be written as a power of another symmetry?

Let $$D=(V,A)$$ be a finite directed graph, and suppose that

• $$D$$ is vertex-transitive,
• $$D$$ is edge-transitive, and
• between any two vertices there is at most one edge, in particular, if $$(v,w)\in A$$ then $$(w,v)\notin A$$.

Question: Is it true that every non-identity involution $$\phi\in\operatorname{Aut}(D)$$ (i.e. $$\phi^2=\operatorname{id}$$) can be written as $$\phi=\sigma^n$$ for some $$\sigma\in\operatorname{Aut}(D)\setminus\{\phi\}$$ and $$n\ge 2$$?

For example, consider the directed cycle below. The 180° rotation is the only involution, and it can be written as three times the application of a 60° rotation.

$$\quad\quad$$

• What about an oriented toroidal grid? Is the "transposition" symmetry a power? Commented Jan 23, 2021 at 14:53

Here's the example I mean:

I'm pretty sure the transposition symmetry here is not a power of another automorphism. Also, it should be vertex/edge transitive.

• So maybe an additional hypothesis of topogical nature (like planarity, genus $0$ or whatever) should be required to ensure an affirmative answer. Commented Jan 23, 2021 at 15:33
• Thank you very much. The suggestions of Sylvain are interesting, but this answer is absolutely sufficient for my purpose and I am happy to accept it. Commented Jan 23, 2021 at 16:12

This answer builds upon Sam Hopkins' suggestion of an oriented toroidal grid, but it's more than a comment. Bottom line: need the grid to be $$2^s$$ by $$2^s$$ where $$s\ge2$$ to get the requested involution property.

So here's a sketch of a grid:

WLOG we can label some vertex as $$(0,0)$$, and then its two out-neighbours as $$(1,0)$$ & $$(0,1)$$. But how do we know that the visual layout corresponds to the only actual two-dimensional grid? $$(1,0)$$ has two out-neighbours we label $$(2,0)$$ & $$(1,1)$$. Critically, we can distinguish these because there is only a single path of length $$2$$ from $$(0,0)$$ to $$(2,0)$$, while there are two paths of length $$2$$ from $$(0,0)$$ to $$(1,1)$$. So we can extend the edge $$((0,0),(1,0))$$ to $$((1,0),(2,0))$$ to $$((2,0),(3,0))$$ to ... etc, getting a "unique straight cycle" (USC) that wraps all the way around the grid horizontally, eventually arriving in $$(0,0)$$ again. Similarly $$((0,0),(0,1))$$ extends to a vertical USC, wrapping all the way to $$(0,0)$$.

By edge-transitivity, the horizontal USCs must have the same length as the vertical ones, so the grid is an $$n$$ by $$n$$ square. Need $$n\ge3$$ since otherwise there are multiple edges between pairs of vertices.

Now we are safe to label all the vertices in the obvious way, as $$(x,y)$$ for $$x,y\in\{0,\dotsc,n-1\}$$, and all the edges similarly as $$((x,y),(w,z))$$.

It's easy to see that the action of an AM on one edge defines its action on the whole graph, so the number of AMs is equal to the number of edges $$= 2n^2$$. Half the AMs are just translations, where the USCs of an edge and of its image are parallel. The others are flips, where the two USCs do meet at one vertex.

Define three AMs $$a$$, $$b$$, $$c$$ by their action on the edge $$((0,0),(1,0))$$ as $$((1,0),(2,0))$$, $$((0,1),(1,1))$$, $$((0,0),(0,1))$$ respectively. So $$a$$ is "right", $$b$$ is "up" and $$c$$ is "$$x$$-$$y$$ flip".

$$a^n = b^n = c^2 = 1$$, $$ab = ba$$, $$cac = b$$, $$cbc = a$$.

Let $$d = ab = ba$$ (called "diagonal"). Then $$cd = dc$$.

A typical flip can be written as $$c{a^p}{b^q}$$.

$$(c{a^p}{b^q})^2 = d^{(p+q)}$$.

So flips have even order dividing $$2n$$. There are hence exactly $$n$$ flip involutions: $$c{a^p}{b^{(n-p)}}$$. Write them as $$cg^p$$, where $$g=ab^{-1}$$.

Suppose $$n$$ has an odd factor $$k$$, so $$n = km$$. Then any AM of the form $$c{g^p}{d^m}$$ taken to the $$k$$th power gives $${(cg^p)^k}*{d^{mk}} = cg^p$$. So these involutions are powers of other AMs, contrary to the request.

On the other hand, suppose $$n$$ is a power of $$2$$, and that a flip involution $$f = h^{2^j}$$ for some AM $$h$$. Then $$f = (h^2)^{2^{j-1}}$$. But, as shown above, $$h^2$$ must be a translation, not a flip, so $$f$$ cannot be a flip either. So, contrary to hypothesis, $$f$$ is not a power of another symmetry.

So to get the requested property it's necessary and sufficient that $$n=2^s$$, where $$s\ge2$$.

• Thanks for the correction! Commented Jan 25, 2021 at 3:47
• TeX note: use $\ge$ \ge, not $>=$ >=. I have edited accordingly. Commented Jan 25, 2021 at 13:40
• @LSpice - thanks for this Commented Jan 25, 2021 at 14:03