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.