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

Cheryl Praeger

Good news for a change. I just heard that Cheryl (my mathematical sister, third most prolific coauthor, and good friend) has been made a Companion of the Order of Australia.

https://www.abc.net.au/news/2021-01-26/professor-cheryl-praeger-receives-companion-order-of-australia/13089958

Congratulations Cheryl!

Posted in Uncategorized | Tagged | 3 Comments

Graphs defined on groups

I’ve been spending time I can ill afford on various questions related to graphs whose vertex set is a group G and which capture some of the structure of G. (I interpret this to mean that the graph is invariant under the automorphism group of G, so I don’t include Cayley graphs; anyway, so much has been said about Cayley graphs that I have little to add.) My notes on this are up to 44 pages already. So I will give a brief summary here. If you are interested in working on this, and would like a copy of the notes, let me know.


The group G will here be finite; that already leads to interesting questions. The graphs I consider are (with the joining rule for vertices x and y):

  • the power graph, one of x and y is a power of the other;
  • the enhanced power graph, x and y are both powers of an element z (equivalently, ⟨x,y⟩ is cyclic);
  • the deep commuting graph, the preimages of x and y commute in every central extension of G;
  • the commuting graph, xy = yx (equivalently, ⟨x,y⟩ is abelian);
  • the non-generating graph, ⟨x,y⟩ is a proper subgroup of G.

These form a hierarchy: the edge set of each graph is contained in that of the next, except possibly the last which is a bit of an outlier, but contains the one before provided G is either non-abelian or not 2-generated.

Several other graphs also appear in the story:

  • the Gruenberg–Kegel graph of G, whose vertex set is the set of prime divisors of the order of G, primes p and q joined if G contains an element of order pq;
  • the intersection graph of a family C of non-trivial proper subgroups of G, where two subgroups are joined if their intersection is non-trivial.

For the graphs in the hierarchy, I also define the reduced graph to be the induced subgraph on the set of non-identity elements of G. (For each graph in the hierarchy, the identity is joined to all other vertices. Ideally we should form the reduced graph by removing all vertices which are joined to all others; the set of such vertices is explicitly known in all cases except for the non-generating graph, and in particular if the centre of G is trivial the only such vertex in all cases except possibly the non-generating graph is the identity.)

To avoid having to make special provision for the non-generating graph too often, I sometimes assume that G is non-abelian and 2-generated. This of course includes all finite simple groups.

Inclusion, equality, and differences

As said above, the power graph, enhanced power graph, deep commuting graph, commuting graph, and non-generating graph (if G is non-abelian 2-generated) form a hierarchy. So a natural question is: when can two of these be equal?

Starting at the top, if G is non-abelian and 2-generated, then the non-generating graph is equal to the commuting graph if and only if G is a minimal non-abelian group. Such groups were all determined by Miller and Moreno in 1904.

The commuting graph is equal to the enhanced power graph if and only if G contains no subgroup Cp×Cq for distinct primes p and q. This is equivalent to saying that the Gruenberg–Kegel graph of G is a null graph.

The enhanced power graph is equal to the power graph if and only if G contains no subgroup Cp×Cp for any prime p. This is equivalent to saying that the Sylow subgroups of G are all cyclic or (if p = 2) generalized quaternion.

The groups in these two results can be determined more or less explicitly. So in particular one can determine the groups whose power graph and commuting graph are equal.

The deep commuting graph is a bit more difficult, but there are criteria for it to be equal to either the commuting graph of the enhanced power graph. Equality of the deep commuting graph and commuting graph holds if and only if the Schur multiplier and the Bogomolov multiplier of G are equal. (I won’t define either of these here; there are references in the notes.)

Given these results it is natural to ask what can be said about the differences. For the “non-commuting, non-generating graph”, Saul Freedman has good results, which will be in his thesis; analysis of the question of connectedness for nilpotent groups is in a paper shortly to appear in the Electronic Journal of Combinatorics.

For most other pairs, very little is known. I have started thinking about the “commuting, non-power graph”, but I can’t say much as yet.

Induced subgraphs

I have discussed this in a rather fragmented way on the blog before, so here is a summary. For each type T of graph in the hierarchy except the power graph, these graphs on finite groups are universal: for every finite graph Γ there is a group such that Γ is an induced subgraph of T(G). Though the results are uniform, the proof techniques are rather different for the different types.

This still leaves an interesting question or two: bound the order of G in terms of &GAmma;; and how large does a group have to be for T(G) to embed all n-vertex graphs?

For the power graph, the situation is a little different. The power graph of any finite group is the comparability graph of a partial order; but any finite graph which is the comparability graph of a partial order is an induced subgraph of the power graph of some finite group. Similar further questions can be asked.

Cographs and twin reduction

A small digression into graph theory here.

Two vertices u,v of a graph are called twins if they have the same neighbours, apart possibly from one another. I will distinguish open twins (equal open neighbourhoods) and closed twins (equal closed neighbourhoods) where necessary. Being equal or twins is an equivalence relation on the vertex set. (No vertex can have both an open twin and a closed twin.)

If two vertices are twins in a graph, we can identify them. This process can be continued until no more pairs of twins remain. The result is unique, independent of the order of reduction. I will call this graph the cokernel of the original graph.


Another description is that two vertices are twins if and only if the transposition interchanging them and fixing all other vertices is an automorphism of a graph. So the automorphism group of the graph has a normal subgroup which is the direct product of symmetric groups on the twin classes.

A cograph is a graph which has no induced subgraph isomorphic to the 4-vertex path P4. The class of cographs is the smallest class of graphs containing the trivial vertex and closed under complement and disjoint union. Any cograph on more than one vertex contains a pair of twins; indeed, a graph is a cograph if and only if its cokernel has just one vertex.

From this it can be shown that the automorphism groups of cographs can be obtained from the trivial group by the two operations “direct product” and “wreath product with a symmetric group”.

Forbidden subgraphs

Various important classes of graphs (such as perfect graphs, cographs, chordal graphs, threshold graphs, and split graphs) can be defined by a list of forbidden induced subgraphs (as we saw above for cographs).

For each such class, and each type T of graph in the hierarchy, we can ask: for which groups G is T(G) in the prescribed graph class? There are results for some cases, but our knowledge is not complete.

A particularly interesting case: For which groups is it true that the power graph is a cograph? Curiously, there is a necessary condition, and a sufficient condition, for this purely in terms of the Gruenberg–Kegel graph; but there is no necessary and sufficient condition in these terms. (The groups PSL(2,11) and M11 have the same GK graph; but the power graph of the first, but not that of the second, is a cograph.

Furthermore, the innocent-looking question “For which prime powers q is PSL(2,q) a cograph?” leads into fairly deep number-theoretic waters; I do not expect a solution any time soon.

I have computed the cokernels of all graphs in the hierarchy for non-abelian fin ite simple groups with orders up to that of M11; there is a ta ble of their numbers of vertices in the notes.

Connectedness

The question of connectedness of some of the graphs in the hierarchy has been well studied. Of course, the question for the various “difference” graphs is much less well studied.

Here is a result which may be of some interest as tying things together. For a finite group G with Z(G) =&nsbp;1, the following are equivalent:

  • the Gruenberg–Kegel graph of G is connected;
  • the reduced commuting graph of G is connected;
  • the intersection graph of non-trivial abelian subgroups of G is connected;
  • the intersection graph of maximal abelian subgroups of G is connected.

Automorphism groups

If G is a non-trivial finite group, then the twin relation on T(G) is non-trivial for any type T in the hierarchy. If g is an element of order greater than 2, then any element h generating the same cyclic subgroup is a twin of g. If no such element exists, then G is elementary abelian, and the result is easily checked directly (type by type).

So the automorphism group of T(G) contains the automorphism group of G, and also the direct product of symmetric groups on the twin classes. But there may be more, and the picture is not entirely clear. In particular, the reduction process can introduce extra automorphisms.

An interesting example of this was found by Colva Roney-Dougal. Take G to be the group PSL(2,16). The automorphism group of its non-generating graph separates the sets of elements of orders 3 and 5. But after twin reduction, these two classes can be interchanged! The automorphism group of the cokernel of this graph is C2×PΓL(2,16).

The nicest possible situation is exemplified by M11. The cokernel of the power graph has 1212 vertices and automorphism group M11.

But of course, if (say) the power graph of G is a cograph, then its automorphism group is built from the trivial group by direct product and wreath product with symmetric groups, and does not reflect the structure of G very well.

More

There is more to say, both about these graphs and about others that can be defined, but that is enough for now.

Posted in mathematics | Tagged , , , | 8 Comments

Alan Hoffman

I have just heard the news that Alan Hoffman has died, at the age of 96.

There is much to say about Alan; I will restrict myself to my own person perspective, and not even all of that; I didn’t know him well, but met him several times and regarded him as a friend.

Alan was interested (among many other things) in eigenvalues of graphs, in particular the smallest eigenvalue, and more particularly still the class of graphs with smallest eigenvalue −2 (or greater). To describe such graphs, it is enough to describe the connected ones.

Alan knew that line graphs have least eigenvalue −2 (or greater, in a few simple cases). One of his results from the 1950s characterized the line graph of the complete graph Kn by its spectrum if n is not equal to 8. (For n = 8, there are three exceptional graphs, characterized by Chang.)

Alan further invented the class of generalized line graphs, which also have least eigenvalue −2. He knew that this class did not capture all such graphs (the Petersen graph, unsurprisingly, being an exception), but he conjectured that “most” connected graphs with least eigenvalue −2 are generalized line graphs, and around 1970 wrote a long manuscript attempting to prove a result along these lines. I never saw this legendary manuscript, so I am not quite sure what it did; I think perhaps “most” meant a lower bound on the minimum valency of a vertex.

Anyway, it was this manuscript which led Jean-Marie Goethals and Jaap Seidel to a geometric analysis, where they embedded the graph as a set of vectors of fixed length in a Euclidean space, any two making an angle of 90 degrees or 60 degrees. They also showed that the lines spanned by such a set could be enlarged to a maximal set, which was “star-closed” (that is, if two lines in a plane make an angle of 60 degrees, then the third line at 60 degrees to both is also in the set). I realised that these star-closed sets were exactly the lines spanned by the vectors in a root system of type ADE. This gave rise to a very simple proof of Hoffman’s theorem, in stronger form: a connected graph with least eigenvalue −2 is either a generalized line graph or one of a finite set (up to isomorphism), all of which were embeddable as above in the root system E8.

I think Alan was very pleased with this theorem (not least because he had no need to struggle to complete his long manuscript). The paper is among my most cited.

So rest in peace, Alan.

Posted in Uncategorized | Tagged , , | 3 Comments

Family

The coincidence of Peter Neumann’s funeral and Eric Lander’s elevation in the last few days has inevitably made me think about family (in the mathematical sense).

First, pictures of my aunts and uncles, brothers and sisters, sons and daughters, taken nearly fifteen years ago at Ambleside in the Lake District.

Fa
mily, 1
Family, 2

Families always have hidden secrets, joys and sorrows; but they do matter. Tim Penttila was in love with projective geometry for as long as I knew him; I well remember his delight when he discovered that he was a descendant of Oswald Veblen, a great pioneer in the subject. Henry Whitehead, who said “Combinatorics is the slums of topology” (this was told to me by Graham Higman, his student and my mathematical grandfather), has a fourth-generation descendant who has a doctorate in combinatorics and who became director of the Whitehead Institute.

Incidentally, Peter Neumann told me that Whitehead was not really Veblen’s student, though they worked together very closely. Well, who knows? Even the Mathematical Genealogy Project admits that Lagrange was not really a student of Euler, being self-taught. In his Miscellany, Littlewood credits (I think) Hardy with the observation that a proof of a theorem with a couple of gaps is like being descended from William the Conqueror with a couple of gaps. (So I am descended from Leibniz with possibly a couple of gaps.)

So this is an opportunity to tell briefly something about Eric. He arrived in Oxford on a Rhodes Scholarship to do research in algebraic topology. But before the term started, he had changed his mind and decided to do coding theory instead. By chance, it happened that I was the only person in Oxford at the time who claimed to know anything about coding theory. (I had worked with Jack van Lint, and at the instigation of Dan Hughes had written the book with Jack which in its latest version is Graphs, Codes, Designs and their Links.) So I got to supervise Eric.

As it happened, I had something much vaguer than a conjecture which I thought he might like to think about. I had observed that there were two techniques in design theory which, where they overlapped, gave similar results. One, going back to the Bruck–Ryser and Chowla–Ryser theorems, had been used by Dan Hughes to investigate automorphisms of designs. It applied whenever there was a prime which divided a certain parameter to an odd power. The other was the construction of a self-dual code from a design, which was later crucial in the nonexistence proof of the projective plane of order 10; it required a prime to divide the same parameter to the first power only. I thought there might be a common generalisation, which would extend the power of the first technique and the scope of the second.

Eric, with a good background in algebraic number theory, took to it immediately. The coding theorists had taken an integer matrix and considered its row space over the finite field with p elements. Eric observed that, if instead you took the row space over the p-adic numbers, then you could reduce it modulo arbitrary powers of p, and get a chain of codes, with the property that duality reversed the order in the chain (so if the power of p involved was odd then the code in the middle was self-dual).

Eric’s thesis took off from there, and at the end he turned it into a book with the title Symmetric Designs: An Algebraic Approach. So, when he came to Ambleside to talk at my birthday conference, he called his talk “The Human Genome: An Asymmetric Design”.

This reminds me of another story, which I have probably told before. It is a family failing (and I mean my real family here) that as we get older we forget that we have told stories before and tell them again to the same people.

The American Mathematical Society had (maybe they still do) a slot for a talk at their meeting for somebody who uses mathematics in their work in another area. One year they invited Eric to talk. On the plane, he was sitting next to someone who was obviously a mathematician, so they introduced themselves to each other. Eric’s companion was amazed. “Not the Eric Lander, of Symmetric Designs: An Algebraic Approach?” Eric told me this with great delight.

Now back briefly to Peter Neumann. At his funeral yesterday, Sylvia mentioned his love of music (he played violin and viola). I was transported back to a room at a British Mathematical Colloquium (not sure where or when), where Peter Neumann and Philip Higgins played some of Bartók’s Duos for Violin. I was absolutely spellbound by this beautiful music, and lost no time in finding a copy of the score. I found that it adapts well to the guitar, with no transposition necessary. A few times in my life I have been fortunate to have a guitar player to perform the duets with.

Posted in history, mathematics | Tagged , | 8 Comments

Eric Lander

One of my first doctoral students, Eric Lander, has been appointed science advisor in Joe Biden’s cabinet:

https://www.sciencemag.org/news/2021/01/biden-appoints-geneticist-eric-lander-science-advisor

I have had so many congratulatory emails that it almost seems as if I have done something good myself …

Posted in Uncategorized | Tagged , | 7 Comments