Power graphs of torsion-free groups

Today a paper on this topic appeared on the arXiv. I will say a bit about its contents, and how it came about.

The power graph of a group G has vertex set G, with an edge from x to y if one is a power of the other; the directed power graph is a directed graph with an arc from x to y if y is a power of x. Various studies have looked at the properties of these graphs as graphs. But the questions discussed here are:

  • If two groups have isomorphic power graphs, do they have isomorphic directed power graphs? Further, is it true that any isomorphism between power graphs is an isomorphism between directed power graphs?
  • What does the power graph tell us about the group? In particular, if two groups have isomorphic (directed) power graphs, must they be isomorphic?
  • As you would expect, all these questions have negative answers in general.

    For finite groups, it is known that the power graph determines the directed power graph up to isomorphism. But it does not determine it uniquely. (In the cyclic group of order 6, the identity and the two generators are all joined to everything, and so the power graph does not determine which element is the identity; the directed power graph clearly does.) The power graph does not determine the group up to isomorphism: for example, any group of exponent 3 has power graph consisting of a number of triangles with a common vertex.

    For infinite groups, things are worse. The Prüfer group Zp (the group of rationals with p-power denominators modulo the group of integers, where p is prime) has the property that its power graph is complete, so we cannot even determine the prime, whereas clearly we can determine p from the directed power graph.

    It seems to be the fact that all elements have finite order that causes the trouble here. So let us banish them, and assume that the group is torsion-free. These groups have the great advantage that, if x = yn, then n is unique, and moreover it cannot happen that also y = xm unless m = n = ±1.

    At once a small problem of definition arises. The identity element is equal to x0 for any element x, so is joined to everything in the power graph. In particular, in the infinite cyclic group, we cannot distinguish the identity from the two generators (much as happens for the cyclic group of order 6 in our earlier example). But, in any other torsion-free group, the identity is the only vertex joined to everything. So, if we change the definition slightly so that edges or arcs are not put in from x to x0, then the identity becomes isolated in any torsion-free group (and only in such groups), and apart from the infinite cyclic group the answers to our questions will not be changed. So we simplify things slightly by making this change.

    Now here are some of the results.

    • If the power graph of H is isomorphic to that of the infinite cyclic group Z, then H is isomorphic to Z, and any power graph isomorphism is a directed power graph isomorphism. [It need not be a group isomorphism, since an element and its inverse have the same neighbours, and so may be interchanged by a graph isomorphism.]
    • If two torsion-free nilpotent groups of class (at most) 2 have isomorphic power graphs, then they have isomorphic directed power graphs.
    • If G is a torsion-free group in which any non-identity element lies in a unique maximal cyclic subgroup (free and free abelian groups are examples of this), then the power graph of G is a disjoint union of connected components, each isomorphic to the power graph of Z with the identity removed, together with one isolated vertex. In particular, if two groups with these properties have the same cardinality, and neither is Z, then they have isomorphic power graphs; and any power graph isomorphism is a directed power graph isomorphism.

    There are also some results about Q, the additive group of rationals, and some of its subgroups. For Q we have the interesting property that any power graph isomorphism is either an isomorphism or an anti-isomorphism (reversing all directions) of the directed power graph.

    The main authors of this paper are St Andrews undergraduates Horacio Guerra and Šimon Jurina, who proved these results as part of their summer research project last year. On Wednesday they took time out from exam revision to present these results in our Algebra and Combinatorics seminar. I wish them good fortune in their exams and in their subsequent careers.

    Advertisements

    About Peter Cameron

    I count all the things that need to be counted.
    This entry was posted in exposition and tagged , , . Bookmark the permalink.

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s