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. Further details to follow.

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

EDI

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 , , | 1 Comment

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

Graphs on groups, 4

Here is a small problem, mixing group theory and number theory, which might appeal to someone.

A couple of definitions. The power graph of a group G has an edge from x to y if one is a power of the other; the enhanced power graph has an edge from x to y if both are powers of an element z.

Every edge of the power graph is an edge of the enhanced power graph. So the clique number of the enhanced power graph is at least as great as that of the power graph. But in the other direction, there is a function f on the natural numbers such that, if the clique number of the power graph is m, then that of the enhanced power graph is at most f(m). The proof below gives a function growing exponentially.

Problem: What is the best possible function here?

So here is the proof. It is easy to see that a maximal clique in the enhanced power graph is a maximal cyclic subgroup of G. (The only non-trivial point in the proof is to show that, if a set of elements of a group has the property that any two generate a cyclic subgroup, then the whole set generates a cyclic subgroup.) So the clique number of the enhanced power graph is the maximum order of a cyclic subgroup.

The clique number of the power graph is not so straightforward. But the power graph of a cyclic group of prime power order is complete; so the clique number is at least as great as the maximum order of a cyclic subgroup of prime power order. Let this number be m. Then the exponent of the group is at most the least common multiple of the numbers 1,2,…,m, and the clique number of the enhanced power graph does not exceed this value. Now it follows easily from the prime number theorem that this lcm is about em.

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

Graphs on groups, 3

Since this stuff keeps growing, I have decided to keep the most recent version on the web. It is now nearly twice as long as the first version I circulated. If you are interested, please take a copy: it’s at http://www-groups.mcs.st-andrews.ac.uk/~pjc/graphs/graphs.html

What is new in this version? A section about cographs and twin reduction has been extended, with the results of computation on small simple groups; there is a note about Cayley graphs invariant under the automorphism group of the group; and a few brief comments about other graphs such as the nilpotency and solvablility graphs of a group, graphs on semigroups, and graphs on rings.

Posted in Uncategorized | Tagged , , , , | 2 Comments

13th Iranian International Group Theory Conference

This week has been rather a rush. As well as the first week of semester (and my first ever experience of on-line undergraduate lecturing), I have been attending the 13th Iranian International Group Theory Conference in Urmia, Iran. (I had to look it up on the map; it is in the very west of the country, in West Azerbaijan province, near the Turkish border.) The main organiser was Mohsen Ghasemi.

Because Rosemary and I were both lecturing on Wednesday, and Iran is 3 hours 30 minutes ahead of us, I was certainly not able to attend all the sessions, though I did do rather better on Thursday than on Wednesday. Here is a very brief sample of what I heard. I’m afraid that, as usual, it will overlaid with various reminiscences and speculations.

Sasha Ivanov talked about locally projective graphs, starting with GL(4,2) and building up to J4. He had a couple of other configurations which have not been fully understood. One seems to give rise to the alternating group of degree 256, the other is still mysterious. If this sounds as if Sasha is still alert to the possibility of a yet unknown sporadic simple group, that seems to be the case. He mentioned an article in the London Mathematical Society Newsletter for January 2021, on Rubel’s problem. In the middle it mentions the Prouhet–Tarry–Escott problem. This concerns two (k+1)-sets of integers which have the same sum of ith powers for i ≤ k. The largest k for which an example is known is 12, and for the known set the difference between the products is 212.39.53.72.112.132.17.19.23.29.31. He remarked that this number resembles the order of a sporadic simple group.

He thought I would probably agree with him. Sorry, Sasha, it looks to me more like a “round” number, a number with more divisors than any smaller number. I don’t know if it is round in this sense, probably not. But typical sporadic groups skip some primes (the Baby Monster, for example, skips the primes between 31 and 47), while round numbers do not. Also the exponents of the primes in a round number are monotonic non-increasing, while this is not so for orders of sporadic groups (O’Nan, for example, has 5 to the first power but 7 cubed).

Still, it is tempting to speculate on a revisionist history, where this example had been discovered in the late 1960s. John McKay would have connected it with something interesting, John Conway would have developed some moonshine associated with it, and a group might have been coaxed into existence.

This reminds me of something that did happen in the late 1960s. I was walking along a street in London, when a van passed me; on the side was written “The Cameron group”, and a 7-digit number. Unfortunately for me it was an odd number.

Another evocative talk for me was by Eugenio Gianelli. He spoke from his office in the University of Florence. It was a really beautiful talk on character theory (proof of a conjecture of Malle and Navarro). But behind him was a poster displaying the finite simple groups in the format of the Periodic Table. (The same poster was used by the Isaac Newton Institute meeting on group theory that I was attending at the start of last year.) Now I visited Florence in February last year to work with Carlo Casolo and Francesco Matucci on integrals of groups (the topic of my conference talk). It was an adventurous trip in a few regards. North Italy was already locked down but Covid had not yet reached Florence, so I was able to make the trip, though storms did their best to stop me: my flight out was a day late because of storm Ciara, and my trip back might have been delayed by Storm Dennis; the pilot flew anyway but it was the bumpiest landing I have had for a long time.

Anyway, they gave me a share of an office in a different building, but I found it better to work in the office which Carlo shared; I spent quite some time sitting there, waiting for inspiration to strike, and staring at this poster.

We got a huge amount of work done in the week, but a month later, Carlo was dead from a heart attack. Francesco and I did our best to sort out the notes he left us with, but we didn’t succeed in understanding everything. So there are open problems there which might have been closed …

Gareth Jones told us about his beautifully simple diagrammatic proof that the modular group has uncountably many maximal subgroups containing no parabolic elements. This means that the Farey graph, familiar to number theorists, is a Cayley graph admitting an action of the modular group in uncountably many different ways. His results extend to other triangle groups too.

He mentioned that this line of research had been started by Bernhard Neumann, whom he described as his mathematical grandfather (his son Peter was Gareth’s and my doctoral supervisor). Bernard also was a pioneer in the material I talked about. Of course Peter died last month, a few days before his 80th birthday.

Last year has left many sad memories. Let us hope that this year will be better.

Posted in events | Tagged , , , , , | Leave a comment

Graphs on groups, 2

I wrote the long post about this to try to write it out of my system. No luck …

I mentioned in that survey that every finite graph is embeddable as induced subgraph in the enhanced power graph, deep commuting graph, commuting graph, or non-generating graph of some finite group. The proofs are all different and require a small amount of ingenuity.

If we start thinking about differences, several further questions arise. For example, the groups I use to show that enhanced power graphs are universal are all abelian, and so in fact (by looking at complements) we see that graphs on groups whose edge sets are the differences of the commuting graph and enhanced power graph are universal.

In fact, with a little more ingenuity, much more can be shown.

Suppose that we have a finite complete graph on n vertices, whose edges are coloured with three colours, say red, green and blue, in any manner. Then we can embed the vertex set in a finite group G in such a way that

  • two vertices joined by a red edge are adjacent in the enhanced power graph;
  • two vertices joined to a green edge are adjacent in the commuting graph, but not in the enhanced power graph;
  • two vertices joined by a blue graph are non-adjacent in the commuting graph.

In other words, the structures with three kinds of pair, enhanced power graph, commuting graph minus enhanced power graph, and non-commuting graph, are universal for finite structures of this kind.

Here is the proof. If p is an odd prime, we make use of the group P, the non-abelian group of order p3 and exponent p2. This is generated by two elements a and b, where a has order p2, b has order p, and the commutator [a,b] is equal to ap.

The proof is by induction on n, the result being clear if n = 1. So suppose that n > 1, and that we have embedded the first n−1 points into a group G so that the three conditions hold. Choose a prime p which does not divide the order of G, and let P be the group defined above. We modify this to get an embedding into the direct product P×G as follows:

  • if {vi,vn} is red, then replace vi by (1,vi);
  • if {vi,vn} is green, then replace vi by (ap,vi);
  • if {vi,vn} is blue, then replace vi by (a,vi).

Finally, we embed vn as the element b.

Then this gives an embedding of the whole n-element structure.

The proof is not so hard, depending on three simple observations:

  • the direct product of cyclic (resp. abelian) groups of coprime order is cyclic (resp. abelian);
  • two elements lying in ⟨a⟩ generate a cyclic group;
  • b and x generate a cyclic group if x = 1, a non-cyclic abelian group if x = ap, and a non-abelian group if x = a.

Obviously there are a number of variants on this using other types of graphs in the hierarchy. Please try one problem of this kind for yourself; or, less ambitiously, take the difference between two types of graph in my hierarchy and decide whether it is universal, and if not, which graphs can be embedded as induced subgraphs.

Posted in doing mathematics, mathematics | Tagged , | Leave a comment