A small problem

In connection with the research discussion about graphs and groups, I began to wonder which finite groups have the property that any two elements of the same order are conjugate. I thought about this, and got a certain distance, and then other jobs crowded it out of my thoughts.

I had become convinced that there are only three such groups, the symmetric groups of degrees 1, 2 and 3, and had got part way to a proof. In the end, not having time to go back to it, I resorted to a well-known search engine. With a little further research I came up with the answer, and with a small problem, which I want to pose.

In 1933, G. A. Miller published a paper in the Proceedings of the National Academy of Sciences of the USA on the problem. (His name is one which has come up a number of times in our researches about graphs on groups.) He showed, in brief, that in a group with this property, the derived group has index at most 2; moreover, if it has index 2, then the group is the symmetric group of degree 2 or 3. He couldn’t deal with the remaining case (though he did reduce it to considering non-abelian simple groups), and the earliest solution of the problem I found was by Patrick Fitzpatrick, in the Proceedings of the Royal Irish Academy in 1985; he used the Classification of Finite Simple Groups to show that the only such group is the trivial group. This was proved again by Walter Feit and Gary Seitz in 1988. (As a student of Peter Neumann, I know better than to say that they reproved the result – he would certainly have reproved me for saying so!)

So the problem I wish to pose is to give a proof of this simple result which does not depend on CFSG.

Posted in open problems | Tagged , , | Leave a comment

Bad times

Apologies for this. If you don’t like reading personal news, especially bad news, don’t persist. I am writing it down in the hope of putting it behind me.

Back in early April, Rosemary had a very bad fall on the Fife Coastal Path. She tumbled over a six-metre cliff into a rocky river bed, full of icy water. I was able to lift her head out of the water, but it was an hour before the ambulance and coastguard were able to get her out of the river on a scoop and into a helicopter to take her to Ninewells Hospital in Dundee. She had multiple fractures to vertebrae and pelvis as well as scalp lacerations, and her right eye had moved out of position. She was in hospital for two months. She is home now, but I am her full-time carer. I don’t mind doing this, but it eats up time and energy, and I know I am not coping well with other things; I try to get some things done but there is no way I can deal with everything that arrives.

The medics expect her to make a full recovery. She can now walk several blocks on elbow crutches, and the eye is moving back into its correct position. But the vertebrae have not yet mended, so she still has intermittent pain. Part of my job is administering painkillers four times a day. Of course I have all the cooking, cleaning, laundry, and so on, as well as helping her wash and dress herself. It will be months rather than weeks before she is recovered, so I will be on the treadmill for a while yet.

I know this is all very mild compared to what she has been through, but one of the worst things I have to deal with is the memory of watching her fall and being completely unable to help. In the first weeks after the accident it took all my mental strength to stop this scene replaying over and over. I am coming to terms with it a bit better now.

So finally an apology for the rather intermittent updating of this blog. I have been to two outstanding on-line conferences over the past couple of weeks: the British Combinatorial Conference and the Portuguese Mathematical Society’s 80th anniversary meeting. Normally I would have reported on some of the wonderful things I learned at these. But because of circumstances I had to skip many conference talks that I would have liked to attend, and have not had time or energy to write about the ones I did hear. I will just say that, at the Portuguese meeting, several plenary talks which appeared at first sight to be some way from my interests turned out to be absolutely fascinating. The BCC plenary talks have already been posted and the Portuguese talks will appear soon, I hope. When this happens I might try to point you to some of my favourites.

Posted in Uncategorized | 11 Comments

A little problem

In connection with the power graphs of unitary groups, I came across the following little number-theoretic conundrum. Can anyone solve it?

Let q be an odd power of 2 (bigger than 2). Show that (q2q+1)/3 is not a prime power unless it is a prime.

Posted in open problems | Tagged , , | 3 Comments

A new constant?

This is an appeal for help. Has anyone come across the constant 2.648102…?

Here is the background, which connects with my previous posts about graphs on groups. We are interested in the clique number of the power graph of the cyclic group of order n. The generators of the group are joined to everything else; there are φ(n) of them, where φ is Euler’s function. These must be in every maximal clique. To them, we adjoin a maximum-size clique of the subgroup of order n/p, where p is the smallest prime divisor of n. Thus the size f(n) of the largest clique satisfies the recurrence f(1) = 1, f(n) = φ(n)+f(n/p), where as above p is the smallest prime divisor of n. (This was proved by Alireza, Erfanian and Abbas in 2015.)

Now, with f defined as above, I conjecture that the ratio f(n)/φ(n) is bounded, and its lim sup is the constant 2.648102….

As you might expect, the largest values of this ratio are realised by the product of the first so many primes.

Posted in doing mathematics, open problems | Tagged , , | 8 Comments

Graphs on groups, 7

Nothing much to report, just a few connections.

My long paper has appeared on-line ahead of publication in the International Journal of Group Theory. You can get a copy here (click on PDF).

Next week, on Wednesday 12 May at 10:00 (British Summer Time, that’s 09:00 UTC), I am speaking at the QMUL day of the London Combinatorics Colloquia.

And, if you want a longer version, I am giving an 8-lecture intensive course at the London Taught Course Centre next month (tentatively 8–9 June). These courses run over a 24-hour period, from lunchtime on Tuesday to lunchtime on Wednesday. Email office@ltcc.ac.uk to register for the course.

Posted in events | Tagged , , | Leave a comment

Graphs on groups, 6

The Groups and Graphs seminar has been running well.

I find that I feel close to many people in the seminar even though most likely we have not met face to face.

So I feel concerned about the Covid wave in India in a way that I probably wouldn’t have done but for this seminar. My thoughts are with them. By comparison, we are in good shape here. I had my first Covid jab (many weeks late, and after a lot of effort, since I had been left off the list), I am staying at home, and there is very little Covid in the neighbourhood.

Please remember the people of India facing this terrible uncertainty and trouble.

Posted in events | 1 Comment


We hear a lot about equality, diversity and inclusion now. Perhaps it would be good to remind ourselves of the formal definition.

  • A and B are equal if, for all x, we have (xA) ↔ (xB).
  • A and B are diverse if this is not the case; that is, there is an x with either (xA) but not (xB), or (xB) but not (xA). This used to be called “inequality”, but the term is now deprecated.
  • A includes B if, for all x, we have (xB) → (xA). The older terms “subset” and “superset” have overtones of class and should be avoided.

Please note that all the above are binary. This is an obvious shortcoming: there is a high-level commission of logicians working on a non-binary version, but it is proving to be a challenging problem.

Posted in Uncategorized | Tagged , , | 4 Comments

Graphs on groups, 5

I gave two lectures on this stuff to a new research seminar on Groups and Graphs, run by Vijayakumar Ambat in Kochi, Kerala. The first was an introduction to the hierarchy, the second was about cographs and twin reduction, why they matter for this business, and questions like “For which groups is the power graph a cograph?”

The lectures were recorded; they are on YouTube here and here.

Posted in events, exposition, open problems | Tagged , , , , | 2 Comments

Hoffman, Lovász and Haemers

At the weekend I attended remotely a memorial session for Alan Hoffman, organised by Bill Pulleyblank. I found it informative, as well as moving.

Hoffman is well-known in the algebraic graph theory community for a number of remarkable achievements, including the theorem on Moore graphs of diameter 2 and the construction of the Hoffman–Singleton graph, his bounds for chromatic number and for independence number in terms of the eigenvalues, and his very influential work on graphs with smallest eigenvalue −2.

He is perhaps even better known in the optimization communnity. According to Jack Edmonds, he was the first person to program the simplex algorithm (at the Rand corporation in the early 1960s), and he has many results on flows including the famous Circulation Theorem. But apparently he was much more interested in theorems than in algorithms. Several of the speakers claimed to have got their start by devising an algorithm for something which Alan had shown to exist.

So it is true to say that Alan Hoffman was a bridge between these two rather different communities. I am firmly on the algebraic graph theory side of the bridge, and was not really aware of the amount that Alan had contributed to optimization.

One of the speakers was Willem Haemers, who last month put on the arXiv a short paper entitled “Hoffman’s ratio bound”. This is the result which asserts that a regular graph of degree k on n vertices with smallest eigenvalue −s has independence number at most ns/(k+s). You should read the paper for the history. Haemers begins by pointing out that Hoffman never published this result, and consequently many people give the wrong reference to it (to Delsarte, or to Lovász, or to the wrong paper of Hoffman).

He was followed by Laci Lovász, who recalled a visit by Hoffman to a meeting in the former DDR when Laci was just beginning his studies. Hoffman spoke about his earlier result, bounding the chromatic number of an arbitrary graph. Lovász took the result back to Budapest and worked on it. He found a beautiful trick which Hoffman would no doubt have loved (though with his habitual modesty he would have admired it without jealousy). Lovász observed that the argument does not depend on the fact that the non-zero entries of the adjacency matrix is 1; any positive numbers will work. So finding the best bound is an optimization problem, which Lovász solved to come up with his famous θ parameter of graphs, related to the Shannon capacity.

Posted in events | Tagged , , , , , | 1 Comment

Three passages

[Dmitri] Egorov [founder of the Moscow School of Mathematics] was a very reserved and modest man, so much so that it would be easy to believe that he lived only for mathematics. […] His publications do not reveal any evidence of the “inner Egorov” — indications of the motivations that were so clear in many of his predecessors […] However, a close study of his life shows that Egorov was a man of deep passions, religious commitments, cultural identity, and political preference. As Sergei Demidov, a leading Russian historian of mathematics, wrote in the post-Soviet period, Egorov “thought that the opinions and beliefs of a person (including his religious views) belonged to an intimate human sphere and were not a subject of discussion.”

Loren Graham and Jean-Michel Kantor, Naming Infinity

For a lot of people, a pronoun is something that can be taken for granted. However, for a growing proportion of the community, there is a heightened level of awareness of the pronoun which represents them. This guidance seeks to explain some of the concepts around pronoun use and to help you develop practice that contributes to creating an inclusive environment for all members of the … community.

Staff equality, diversity and inclusion guidance, University of St Andrews

All through the day

I me mine, I me mine, I me mine

All through the night

I me mine, I me mine, I me mine

Now they’re frightened of leaving it

Everyone’s weaving it

Coming on strong all the time

All through the day I me mine

George Harrison, “I me mine” (the last song recorded by The Beatles)

Posted in Uncategorized | 5 Comments