Graphs and groups

Last week I gave a short talk at the London Taught Course Centre open day. The LTCC is an organisation run by a consortium of universities and colleges in the London area, putting on courses for PhD students to broaden their mathematical background. The purpose of the open day was to help undergraduates or Masters students thinking of doing a PhD by putting a variety of options (subjects and institutions) before them.

I decided that, rather than advertise my subject or my institution, I would try to give an example of research, by talking about a recent result of mine. I had 30 minutes scheduled, but because of the severe weather the programme was curtailed and I had to compress it into just 20 minutes. Not much time for the purpose.

Here is a summary. More details should be available on the LTCC website.

Groups are very highly structured algebraic objects, while graphs are much looser. For example, there are just five different groups with eight elements, but 12346 different 8-vertex graphs. But the two subjects have various points of contact. For example, any graph has an automorphism group; and indeed several of the sporadic finite simple groups were constructed as automorphism groups of interesting graphs.

My talk was about the reverse direction. Given a group, construct a graph from it, which captures some information about the group. There are several ways of doing this, but the particular one I discussed is the power graph of the group. This comes in undirected and directed versions. I learned about it last summer at the British Combinatorial Conference when Shamik Ghosh from Kolkata asked a question about it.

The power graph comes in two versions. The directed power graph of G has the elements of G as vertices, with a directed edge from b to a if a is a power of b. The undirected power graph is obtained simply by ignoring the directions; in other words, a and b are joined by an undirected edge if one is a power of the other.

It is clear that the directed power graph carries much more information about the group. It is a preorder (a reflexive and transitive relation) on the group. From a preorder, we derive an equivalence relation (two elements are equivalent if there are directed edges in both directions between them – here, this means that they generate the same cyclic subgroup), and a partial order on the set of equivalence classes. In a finite group, the identity is the unique minimal element (it is a power of everything), and the elements that cover it are elements of prime order; the prime p in question is determined by the fact that the size of the equivalence class is p–1. From this it is possible to work out the orders of all elements. In other words, the directed power graph tells us the number of elements of each order in the group.

Shamik Ghosh’s question became, after some discussion, the following:

If two finite abelian groups have isomorphic undirected power graphs, must the groups themselves be isomorphic?

(Both conditions “finite” and “abelian” here are necessary.) After some email exchanges, we had the proof, and had written a paper.

At the start of last term, I gave a talk about this, and offered to buy a drink for anyone in the audience who could answer the following question:

If two finite groups have isomorphic undirected power graphs, must they have the same number of elements of each order?

Shamik’s and my proof for abelian groups had first shown that two such groups must have the same number of elements of each order. For abelian groups, this information determines the group completely.

But nobody took up the challenge, except for my colleague John Bray, who made a first step, and I had to do the work myself. To my surprise, the final result was the following, beautifully clean, theorem:

If two finite groups have isomorphic undirected power graphs, then they have isomorphic directed power graphs.

In other words, contrary to our previous intuition, the undirected and the directed power graph of a finite group carry exactly the same information!

Of course, this settles the above question (so I had to buy myself that drink), and implies the theorem that Shamik and I had proved earlier.

As always in research, a result like this raises many more questions than it settles. Here, briefly, are a few.

  • Given a (directed or undirected) graph, how do we tell whether it is the power graph of a group? What is the computational complexity of deciding this?
  • What can be said about the number of groups of order n which are not determined by their power graphs, or the maximum number of non-isomorphic groups of order n which have isomorphic power graphs?
  • Can “natural” graph-theoretic properties of the power graph of G, such as chromatic number, be related to “natural” group-theoretic properties of G?
  • What is special about groups? Does the theorem hold more generally, e.g. for classes of semigroups or loops?
  • For infinite groups, what extra information do we need to distinguish groups with the same undirected power graph but different directed power graphs?
  • What about other graphs defined from groups?

Who knows; a successful assault on one of these might be the start of a PhD and a career as a mathematician.

Advertisements

About Peter Cameron

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

7 Responses to Graphs and groups

  1. Qiaochu Yuan says:

    As far as the last question goes, a beautiful choice is the “representation graph” of a finite (or compact) group G equipped with a particular finite-dimensional representation V. This is a graph whose vertices are the irreducible representations of G, where the number of directed edges from V_i to V_j is the multiplicity of V_j in V_i \otimes V. When V is two-dimensional and faithful these graphs have a very special form; they’re (affine) Dynkin diagrams! This observation is due to McKay; I’ve been writing about it on my blog.

  2. Yes, an example of the wonderful ubiquity of the Dynkin diagrams in mathematics!

  3. Mary Flagg says:

    I know this is an old post, but I just found the paper and read it yesterday. I am interested in infinite abelian groups. I know that infinite abelian groups are not uniquely defined by their power graph, but if you fix the prime p, are infinite p-groups uniquely defined by their graph? I am particularly interested in nonsplit p-adic modules of torsion-free rank one. I know that they are uniquely defined by their endomorphism rings, and even the Jacobson radical of their endomorphism rings, but I’d like to say something about the automorphism group. And I have in my mind’s eye a picture of the nonsplit group as an extension of a torsion-free group by a torsion group, or vice-versa with some sort of tangled connection graph that indicates how the connection is made. An isomorphism of the group has to some how respect this tangle. But I still have not figured out how to define a graph for my groups that reflects this idea. Any ideas?

  4. That’s a good question. Things are a bit hectic at the moment, but I would like to think about that if I have a bit of time. Thanks for raising it!

  5. Imran says:

    I want to ask a question…that If we have a finite presentation of a group, but order of the generators are unknown, then can we draw a cayley graph of that group?? if yes, then by which mean

    • If you are just given a presentation of a group, the abstract construction of the Cayley graph is defined in the usual way, but we might know very little about it. From a presentation, we can’t always tell whether the group is trivial, finite or infinite, whether two generators are equal or not, and so on.

  6. Pingback: Introduction – vynmath

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