Conference for Colin McDiarmid

Corpus creatures

In Oxford at the weekend, on a rather flying visit from St Andrews, for a conference to mark Colin McDiarmid’s retirement. Colin was a student of Dominic Welsh, a tutor at Corpus Christi (the college next door to Merton), and a neighbour of mine in North Oxford for many years. The theme of the conference was “Probabilistic Combinatorics”, but that was not all that was on the menu!

I will revert to my usual practice of describing only a few of the talks.

Joel Spencer opened proceedings with a wonderful talk on the logic behind Galton–Watson trees, in particular, an explanation for why some questions about them throw up “wrong” solutions. He began with a provocative quote from Peter Jagers’ account of the history of branching processes (you can find the original here):

Rarely does a mathematical problem convey so much of the flavour of its time, colonialism and male supremacy hand in hand, as well as the underlying concern for a diminished fertility of noble families, paving the way for the crowds from the genetically dubious lower classes.

Apart from the mathematics, his talk was full of interesting terminology: “green child” (shades of Herbert Read), “old China”, “draconian fecundity”, and “strange logic” among them.

Angelika Steger talked about “robustness”. What is this? Dirac’s classical theorem about Hamiltonian cycles can be phrased like this. If you give an opponent a complete graph, and allow her to delete edges, but with the restriction that fewer than half of the edges through any vertex can be removed, the opponent cannot destroy the property of containing a Hamiltonian cycle. Accordingly, we say that the robustness of the complete graph for Hamiltonian cycles is 1/2. Angelika went on to several related problems including the square of a long cycle in a random graph.

That evening, at dinner, Dominic Welsh spoke movingly about his former student, and Colin was clearly very touched.

Next morning Alex Scott opened the proceedings, bringing us up-to-date with his joint work with Maria Chudnovsky and Paul Seymour. They are tackling questions of the form “If G is a graph with large chromatic number, must G contain either a large clique or a large (something)?” or, phrased another way. “Is it true that, in (something)-free graphs, chromatic number is bounded above by a function of clique number?” He told us quite a lot about forests of chandeliers, but in the end came to the conclusion that they are “not the answer to everything”.

For me the highlight of the meeting was the talk by Jorge Ramírez-Alfonsín. Starting from the “jugs of wine” problem, on which he had worked with Colin, he turned to aspects of the Frobenius problem: given a finite set of positive integers, which non-negative integers can be expressed as non-negative integer combinations of them? (In other words, given a set of values of stamps, which amounts of postage can be paid exactly by putting the right stamps on an envelope?) If S is this set, then S is an additive semigroup, and is also partially ordered by the relation that x ≤ y if yx is in S. He was concerned with computing the Möbius function of this poset. Its generating function is a rational function, and is the inverse of the Hilbert series of S (analogous to the fact that the Dirichlet series of the number-theoretic Möbius function is the inverse of the Riemann zeta function).

Posted in events | Tagged , , , , , | 2 Comments

A puzzle for you

The Petersen graph is perhaps the most famous graph of all. It has ten vertices, fifteen edges, valency 3, and no triangles. Since the complete graph on ten vertices has 45 edges and valency 9, one might ask whether the edge set of the complete graph can be partitioned into three copies of the Petersen graph (as Allen Schwenk did in 1983 in the American Mathematical Monthly). Four years later, he and Jack van Lint’s problem solving group O. P. Lossers in Eindhoven independently gave an elegant solution, which I described here.

Indeed, their argument shows more. It is possible to find two edge-disjoint copies of the Petersen graph in K10; the argument shows that the remaining 15 edges necessarily form a bipartite graph. Since the Petersen graph is definitely not bipartite, this settles the original question.

Another graph rather similar to the Petersen graph is the Clebsch graph, which has 16 vertices, 40 edges, valency 5, and no triangles. Indeed, there is a close relationship: the subgraph on the non-neighbours of a vertex in the Clebsch graph is the Petersen graph.

The Clebsch graph can be constructed by taking as vertex set a symbol *, the set {1,…,5}, and the set of ten 2-element subsets of {1,…5}. Join * to all of {1,…,5}; join points in this set to pairs containing them; and join two pairs if they are disjoint.

So here is a puzzle. The solution is here.

Suppose we delete the edges of two edge-disjoint Clebsch graphs from K16. What can we say about the graph formed by the remaining edges?

Posted in Uncategorized | Tagged , , | 7 Comments

Discrete mathematics in Derby

Derby ram

This week I have been at a conference on “Theoretical and Computational Discrete Mathematics” at the University of Derby, under the auspices of the Institute for Mathematics and its Applications.

The University of Derby was founded as the Derby Diocesan Institution for the Training of Schoolmistresses in 1851 and became one of the “new universities” in 1992. Finding mathematics on their website is difficult; it is in the college of engineering and technology, rather than a nnumber of equally plausible sounding colleges, and is part of the school of computing and mathematics. The order is significant; mathematics follows computer games, computer science and information technology in their list of subject areas. The mathematics website, when I found it, was entirely about teaching, with no mention of research or staff list. So I had little idea what to expect.

Peter Larcombe, head of mathematics, introduced the conference, and told us that this is the first ever mathematics conference in Derby, but they are hoping to make it the first of a series, possibly every other year. I wish them success in this! Then Chris Linton, current IMA president, told us a bit about the IMA and what it does.

I spoke first, about synchronization, which you have heard enough about if you read what I put here. There was quite a lot of interest, including a question about whether you can produce a parameterised version of the result that finding the shortest reset word for an automaton is NP-hard.

Other talks on the first day:

  • Armen Petrosyan talked about things he called “arithmetic graphs”. The vertex set is a set N of positive integers, possibly with repetitions; there is another set M of positive integers, and you join two vertices if their sum is in M. Taking M={1,2,3} and N={3,4,5} you get the famous right-angled triangle known to the Egyptians, which he calls the “Egyptian graph”. The bulk of his talk consisted of defining a notion of “information” based on the numbers on the edges of the graph, finding representations of various molecules as arithmetic graphs (where N is the set of atomic weights of the atoms), and then finding that various physical properties of the molecules such as solubility in water are highly correlated with “information” (all his reported correlations are over 0.9). Mysterious!
  • Colin Wilmott gave a lovely talk about quantum circuits. Most quantum gates have one input and one output, but you need a gate with 2 in and 2 out, called “controlled NOT” or CNOT. The CNOT gate is the most difficult to implement so he wants to find a circuit for a given job which uses the fewest CNOT gates. This led to some interesting questions about linear recurrences.
  • Dorin Andrica from Romania was introduced as the person who conjectured that the difference between the square roots of consecutive primes is always less than 1. He started his talk with the discussion of “derivatives”, real functions f which are derivatives of some other function. The class of derivatives is larger than the class of continuous functions but smaller than the class of “Darboux functions” (those satisfying the Intermediate Value Theoreom). Trying to construct derivatives of certain specific forms such as products of functions of the form cos(a/x) led to combinatorial questions about Erdős–Surányi sequences, with some interesting results and open problems. Here was someone whose mathematical mansion has no internal walls!
  • Robert Hancock, a St Andrews undergraduate now working with Andrew Treglown in Birmingham, talked about their generalisations of Cameron–Erdős to sets excluding solutions of other linear equations such as px+qy = rz. They have some very precise estimates.
  • Ovidiu Badgasar talked about Horadam sequences, certain special classes of solutions to linear recurrence relations. He asked a very simple question: for what values of the four parameters (the two coefficients in the recurrence and the two starting values) can such a sequence be periodic? Some nice formulae and pretty patterns in the complex plane emerged.
  • Ibrahim Ozbek presented a new threshold secret sharing scheme. (This is a scheme which shares a secret among n people, such that any k of them can recover the secret if they cooperate, but k−1 can get no information whatever.) His example is built from error-correcting codes. We take a t-error-correcting code which can’t correct any t+1 errors; the secret is a word in this code. In essence, it goes like this. The “dealer” chooses n = t+k positions and makes errors in those positions. He also chooses n words from a 1-error-correcting code, such that the first letter of the ith word is equal to the ith coordinate which was changed in the secret; he deletes this first letter and gives the rest to the ith participant. Now the ith participant can recover the deleted coordinate of his word, by putting any old rubbish there and then correcting; so k of the participants can change the published word to one with only nk = t errors, which they can then correct, but fewer than k participants cannot correct the errors.
  • Michael Alphonse talked about an algorithm to find the domination number of a circulant graph with two step lengths.

The second day’s fare:

  • Vadim Lozin explained some very interesting stuff about structural reasons why some graph problems are hard. He began with the observation that the independent set problem is NP-complete, but the matching problem (which is the independent set problem in line graphs) is polynomial (Jack Edmonds’ famous algorithm). Now line graphs form a hereditary class defined by nine forbidden subgraphs, one of which is the claw. The claw is the one that counts. The independent set problem is polynomial in graphs forbidding a claw, but is NP-complete in the class of graphs forbidding the other 8 forbidden subgraphs for line graphs. He went on from there to his theory of boundary classes, a bit technical, but containing some lovely results and a very nice conjecture.
  • Jessica Enright has worked for the Scottish Epidemiology Centre, and had looked at the question: given a graph, how many edges to we have to remove to break it into connected components of size bounded by a given constant? Even the decision problem is NP-complete. However, for graphs of bounded treewidth, there is an algorithm with time linear in the number of vertices, the constant being a function of the treewidth bound (in other words, the problem is fixed parameter tractable). Remarkably, it turns out that the graph of cattle movements between Scottish farms has extremely small treewidth, so the methods are applicable. This seems to me the real mystery from her talk. Afterwards, we had a discussion about this, and decided that perhaps networks designed by humans have small treewidth (because large treewidth makes the graphs hard to think about), while those that evolve by some process may have large treewidth. For example, the “neighbour” relation on Scottish farms (two farms adjacent if they share a boundary) has large treewidth.
  • Nicholas Korpelainen talked about cliquewidth, a related parameter (perhaps). For a hereditary graph class, being well quasi-ordered by induced subgraphs is related to bounded cliquewidth (though a conjecture that these are equivalent has recently been refuted).
  • Yury Kartinnik talked about finding minimum-size maximal k-matchings (sets of edges which are independent in the k-th power of the given graph.
  • Kitty Meeks gave a nice talk about counting induced subgraphs with some particular property. There are six versions of the problem she considers: does such a subgraph exist? can we count them approximately? can we count them exactly? can we find one? can we sample at random? can we find them all? For a given type of subgraph, some of these problems may be tractable, but there are relationships: for examole, if we can solve the decision problem affirmatively then we can find a witness. For example, for a k-clique, delete vertices one at a time until there is no longer a k-clique; the last deleted vertex must be in a clique, so delete it and replace k by k−1.
  • Shera Marie Pausang found Nash equilibria for the “inspection game” where an inspector with limited resources has to inspect a number of people who may or may not be complying when the inspector arrives: a very practical problem!
  • Eric Fennessey talked about some of the practical problems he has to deal with in his daily job at Portsmouth dockyard looking after the navy’s destroyers. The problems seem remarkably basic. One of them is as follows. We have a number of bags of jelly beans, each bag labelled with the number and total weight of beans it contains. Find maximum-likelihood estimators for the mean and variance of the weight of a jelly bean. He remarked that for the variance he has to assume that the distribution of weight is normal, which of course means that there is a non-zero probability that a jelly bean has negative weight!
  • Fionn Murtagh talked about a hypermetric, or p-adic, approach to problems of clustering in large datasets. He remarked that this sort of thinking has been used in publications on psychoanalysis (Ignacio Matte Blanco), fundamental physics (Igor Volovich), and cosmology.
  • I.-P. Popa talked about linear discrete-time systems in Banach spaces.
  • Hitoshi Koyano said that, while a lot of data consists of numbers, for which there are well-developed statistical techniques, increasing amounts of data consist of strings, where techniques are much less developed; he is developing techniques for this.
  • Finally, Sugata Gangopadhyay talked about a subject close to my heart, bent functions; specifically, cubic bent functions which are invariant under cyclic permutation of the variables (he calls this property “rotation invariance”). A bent function is a Boolean function which lies at maximum Hamming distance from the set of linear functions. He is interested in finding bent functions at maximum distance from the quadratic functions. (In fact, it is not obvious that the functions furthest from quadratic functions are necessarily bent, but that is another question!)

A small but extremely wide-ranging conference; I look forward to the next one.

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

Guessing numbers of graphs

A paper, “Guessing games on triangle-free graphs”, by Anh Dang, Søren Riis, and me, has just appeared in the Electronic Journal of Combinatorics. Here is a brief discussion of what it is about. It is always a pleasant surprise when highly symmetric structures like the Higman–Sims graph turn up playing an important role in a topic far away from finite group theory (in this case, network coding).

Guessing number

The guessing number of a directed graph is a parameter arising in network coding, and was introduced by Søren Riis. You don’t need to know that background in order to understand the problem; just bear in mind that, even if it looks a bit artificial, there is an important practical problem underlying it.

The guessing game works like this. Each of n people is wearing a hat, of one of q colours. Players cannot see their own hats, and indeed they cannot see all the other hats. There is a directed graph G whose vertices are the players, and each player can see only the hat colours of his/her out-neighbours. The task of the players is for each player to guess his or her own hat colour. It is a cooperative game, the aim being to maximise the probability that all guesses are correct (assuming that the hat colours are randomly assigned).

If the players guess at random, then the probability that all guesses are correct is 1/qn. To see that considerable improvement is possible, consider the case of the complete directed graph, where each player can see the hats of all other players. In this case, it is possible to achieve a probability 1/q that all guesses are correct, by the following strategy. Regard the hat colours as elements of the integers modulo q. The players agree beforehand to assume that the sum of all the hat colours is zero mod q. The probability that this assumption is correct is 1/q. Now each player makes this assumption, and guesses that his/her own hat colour is minus the sum of all the others; if the assumption is correct, then all players guess correctly.

For information-theoretic reasons, we take a measure of the success of a strategy to be the logarithm, to base q, of the factor by which the probability of success is improved using that strategy, compared to guessing at random. Thus, for the complete directed graph, the above strategy gives the value n−1.

The guessing number gn(G,q) is defined to be the best value which can be achieved by any strategy, assuming that the best strategy is used; that is, the maximum over all strategies. The asymptotic guessing number gn(G) is the limit of this value as q→∞. (It can be shown that this limit exists, even though the guessing number is not a monotone function of q.) It is not hard to show that the guessing number of the complete directed graph is n−1, and that the strategy given is optimal.

From now on, we consider undirected graphs (with the convention that an undirected edge is a pair of directed edges, one in each direction).

Fractional clique cover number

A fractional clique cover of a graph G is a weighting of the cliques of G with real numbers from the unit interval [0,1] with the property that, for any vertex v of G, the sum of the weights of the cliques containing v is at least 1; it is regular if the sum is equal to 1 for every vertex. The fractional clique cover number is the minimum, over all fractional clique covers, of the sum of the weights of all the cliques. It can be shown that the same minimum value is obtained if we restrict to regular fractional clique covers.

I won’t give the general proof, but in the special case where there is an exact covering of the vertices by d cliques, it is easy to see that the guessing number is at least nd: each player lies in exactly one of these cliques, and the players in that clique use the guessing strategy defined above for a complete graph.

Christofides and Markström showed that, for an n-vertex graph G, the guessing number is bounded below by n−κ(G), where κ(G) is the fractional clique cover number of G. They showed, moreover, that this bound is attained for various classes of graphs including perfect graphs, odd cycles, and complements of odd cycles. On the strength of this, they conjectured that the bound is always attained.

Triangle-free graphs

An obvious test case consists of triangle-free graphs, where the only cliques are vertices and edges. Clearly, the fractional clique cover number is at least n/2 in such a graph. In a regular graph, this bound is attained: if the valency is k, give each edge the weight 1/k.

Our paper shows that the bound of Christofides and Markström can be far from the truth, by using the famous triangle-free strongly regular graphs which I discussed here: the Higman–Sims graph on 100 vertices and various of its subgraphs.

The proof depends on two simple ideas.

  • Suppose that a triangle-free graph is regular with valency k, and has the property that any two non-adjacent vertices have exactly μ common neighbours. Then the adjacency matrix A of the graph satisfies AJ = JA = kJ and A2 = kI+μ(JIA), where J is the all-1 matrix. This is a simple exercise in matrix multiplication.
  • Given a graph G on n vertices, let M be a square matrix of order n (whose rows and columns are indexed by vertices of G) with entries from the finite field of order q, having the properties
    • the diagonal entries of M are not zero;
    • if the off-diagonal (i,j) entry is non-zero, then i and j are adjacent in G.

    If M has rank d, then the guessing number of G is at least nd. This is shown by making the assumption that the assignment of hat colours is a vector in the null space of M (this assumption has probability 1/qn−d); each player makes this assumption, looks at the corresponding row of M, and computes his/her hat colour from the assumption that the linear combination of hat colours using the player’s row of the matrix as coefficients is zero.

Now the Higman–Sims graph satisfies our assumptions with k = 22 and μ = 6. From this it is easy to show that, over the field of three elements, M = A+I has rank 23, so that the guessing number is at least 77; the Christofides–Markström lower bound is 50. (Working mod 3, we have A2 = I, so that M(M+I) = 0, so the eigenvalues of M are 0 and −1. Now the principal submatrix corresponding to the 22 neighbours of a point is the identity, and the all-1 vector is not in their span – it would have to be their sum, but each non-neighbour has coefficient 0 in the sum. So the rank is at least 23. It is not hard to show that these 23 vectors span the row space, so we have equality.)

Moreover, this graph can be “blown up” to give an infinite family of examples. Further examples come from the other triangle-free strongly regular graphs.

As an aside, we know that the asymptotic guessing number of the Higman–Sims graph is at least 77, and at most 78. What is it? (Note that guessing numbers are not necessarily integers!) Another open problem is whether there exist triangle-free graphs G on n vertices with with gn(G) > 78n/100.

Posted in exposition, mathematics | Tagged , , , , | 1 Comment

The Prophet

On Friday, in a bookshop, I picked up a book and started leafing through it. Suddenly, I was transported back more than forty years.

In the summer of 1975, before my first child was born, while her mother was doing an Open University summer school in Norwich, I took a short holiday and walked, hitch-hiked and took trains around Norfolk. I saw the stone-age flint mines at Grimes Graves, whose produce was exported along the Icknield Way to much of southern Britain. I saw the lavender mill in Fring during the few weeks of lavender harvest (and I smelt it long before I saw it). I swam in the North Sea at Cromer, having to wade a long way out to get to waist-deep water. In a marsh between land and sea, I saw a pair of swans in heraldic pose, their necks making the shape of a heart.

During my travels, I arrived in Kings Lynn. I found a cheap bed-and-breakfast where the mattress sagged horribly, the room reeked of stale smoke, and an overfull ashtray spilt its contents over the carpet. But the Kings Lynn Festival was about to start, so I stayed for a few days. I went to a concert by Jake Thackray, at which he sang two of his translations of Georges Brassens songs, the famous “Brother Gorilla” and another one I have never heard since, “Stepping Stones”. I saw an exhibition of batik pictures of fabulous monsters and mythical beasts by Thetis Blacker, and bought her book, A Pilgrimage of Dreams, expecting more such pictures but finding instead something even more striking.

The Festival was opened with a service in the enormous church. During the service, there was a reading I didn’t recognise. I was struck by it, especially the last two lines, which stuck in my mind:

Beauty is eternity gazing at itself in a mirror.
But you are eternity and you are the mirror.

I searched sporadically for these lines. (Odd it seems now but, in those pre-Google days, this was not easy.) After a while I forgot all about it.

But yesterday, there they were, in Kahlil Gibran’s The Prophet.

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

The man who knew infinity

Apostolos Doxiadis is someone who has been mentioned several times here. He is responsible (at least in part) for several remarkable works on or about mathematics: a novel (Uncle Petros and Goldbach’s Conjecture), a graphic novel (Logicomix, with Christos Papadimitriou), and a book of essays about mathematics and literature (Circles Disturbed, with Barry Mazur). On one occasion, we met up in London, and he offered to give a lecture to my first-year Mathematical Structures students at Queen Mary.

Out of the blue, he contacted me last week to invite me to a premiere of the new biopic about Ramanujan, based on the book of the same name by Robert Kanigel. It is a while since I read Kanigel’s book, but I have also read Hardy’s book on Ramanujan and Littlewood’s Miscellany, so I had a good idea what to expect.

The film, which goes on general release in Britain early next month, stars Dev Patel as Ramanujan and Jeremy Irons as Hardy. The bones of the story are: Ramanujan, a clerk in Madras with little education, sent letters to Hardy and other British mathematicians containing lists of his mathematical discoveries. The others dismissed him as a crank, but Hardy recognised his genius and brought him to Cambridge, describing it later as the one romantic incident of his life.

As well as the huge culture clash that Ramanujan had to contend with in Britain, the film brings out well the clashes between the two principals: Ramanujan trusted his intuition while Hardy was a stickler for proof; Ramanujan was a devout Hindu who attributed his intuition to the goddess Namagiri, while Hardy was an equally devout atheist. Yet somehow these two disparate characters hit it off and produced some extraordinary mathematics. Their interaction is well portrayed in the film, in a low-key way as befits the formality of Cambridge at the time of the first world war.

Indeed, I thought it was a very good film altogether. Compared to recent biopics of Turing and Hawking, it was remarkably accurate, and yet had a real story to tell, and told it well. Perhaps it was stretching a point a bit to have Hardy come close to admitting belief in God at the end, but it worked well in the drama.

What the film didn’t show was anyone actually doing mathematics. I guess the reason for this is clear enough. Also, I think there were a couple of anachronisms: I am not sure that anyone would have called Hardy “Harold”, though I don’t really know; and Major McMahon introduced his subject as “Combinatorics”, a word which was surely not used then (I think “combinatorial analysis” might have been more accurate), and described it with the words “glorified dice-throwing” which I am pretty sure were invented by Kanigel in his book to explain the subject.

I thought for some time that the film-makers had resisted the temptation to use the famous story about Hardy’s taxicab, but in the end they overdid things by putting it in twice: one of the very few flaws in the film.

Anyway, my advice is: see it, and take your non-mathematical loved ones to see it too. They may get some clue about what drives a mathematician.

I was struck recently when I read this passage in E. R. Dodds’ The Greeks and the Irrational, describing the actions of the gods and their agents, the Erinyes and moira, in the Iliad:

… The recognition, the insight, the memory, the brilliant or perverse idea, have this in common, that they come suddenly, as we say, “into a man’s head”. Often he is conscious of no observation or reasoning which has led up to them. But in that case, how can he call them “his”? A moment ago they were not in his mind; now they are there. Something has put them there, and that something is other than himself. More than this he does not know. So he speaks of it noncommittally as “the gods” or “some god”, or more often (especially when its prompting has turned out to be bad) as a daemon.

Every mathematician knows the experience of sudden illumination, an idea which will certainly make the proof work, so that no verification of this is needed for utter conviction. Where does this come from? We may have theories, but we can’t know for certain. Ramanujan is completely justified in crediting his to the goddess Namagiri, just as Gauss is to “the grace of God”.

Apparently, Namagiri was like a personal goddess to Ramanujan. In another context the Portuguese poet Fernando Pessoa said, “As each fountain has its own deity, might not each man have a god all his own?”

Posted in events, media | Tagged , , , | 3 Comments

The power graph yet again

Five years ago, I posted a short update on the power graph of a group. Now, finally, the paper resulting from this has appeared on the arXiv; my coauthors are Ghodratollah Aalipour, Saieed Akbari, Reza Nikandish and Farzad Shaveisi.

I don’t intend to describe all the content of this 22-page preprint here. I will mainly just draw attention to a new construction which we introduce in the paper, and highlight some of the things we don’t know about it.

The power graph

The power graph of a group has vertex set the group, with an edge between two elements if one is a power of the other. (It is by nature a directed graph, indeed it is a partial preorder, with x ≤ y if x is a power of y; but the undirected power graph determines the directed power graph up to isomorphism.)

One of our results is that the clique number of the power graph of any group is at most countably infinite. Is the same true for the chromatic number? We can only prove this in special cases (free groups, periodic groups, abelian groups).

The commuting graph

A much more studied object is the commuting graph, in which two elements are joined if and only if they commute. In this graph, central elements are joined to all other vertices, and it is customary (when asking questions about the connectedness or diameter) to delete these elements. Indeed, with this convention, Michael Giudici and Chris Parker refuted a conjecture of Jafarzadeh and Iranmanesh by showing that the diameter of the commuting graph of a finite group is unbounded, although earlier Morgan and Parker had proved that the diameter is at most 10 if the group has trivial centre. I reported on these developments here.

But, for what follows, I need to change the convention so that the centre is included. Now it is clear that the power graph is a spanning subgraph of the commuting graph: if x is a power of y then certainly x and y commute.

The new object

We define a new graph called the enhanced power graph. In this graph, again the vertex set is G: two vertices x and y are joined if they are both powers of some element z.

The power graph and commuting graph have the property that, if H is a subgroup of G, then the graph associated to H is an induced subgraph of that associated with G. The implicit existential quantifier in the definition of the extended power graph makes it not obvious that it shares that property; this can be seen by reformulating it: x and y are joined in the enhanced power graph if the group they generate is cyclic.

A clique in the enhanced power graph of a group is a cyclic or locally cyclic subgroup, and hence is at most countable. Again, we don’t know whether the chromatic number of the enhanced power graph is at most countable.


It is clear that the enhanced power graph lies between the power graph and the commuting graph. In the paper, we tackle, and solve (more or less), the question of when two of these graphs can be equal in a finite group.

The argument turns on looking at the direct product of two cyclic groups of prime order. In Cp×Cp, the generators of the two factors are joined in the commuting graph but not in the enhanced power graph; so if these two graphs are equal for a group G, then G cannot contain such a subgroup, and hence its Sylow subgroups are cyclic or generalised quaternion, which leads to the required characterisation.

On the other hand, if p and q are distinct primes, then in the group Cp×Cq, the generators of the factors are joined in the enhanced power graph but not in the power graph; so if these two graphs are equal, then elements of distinct prime order can never commute, so that the prime graph of the group is a null graph. Then a classification of groups with disconnected prime graph (due to Gruenberg and Kegel) can be invoked unless the group G is a p-group for some prime p.

These results assume that the group is finite. Can anything positive be said for infinite groups? (We give a classification of soluble groups with power graph equal to commuting graph without assuming finiteness.) Another open question for infinite groups is when the power graph or enhanced power graph is equal to the commuting graph after deleting central elements.

Three problems

Thus, for most groups G, these three graphs form a strict hierarchy. But what properties do differences between the graphs have? For example, for which groups G is it the case that the edges of the commuting graph not in the enhanced power graph form a connected graph (when central elements are deleted)? For which groups do the edges of the enhanced power graph not in the power graph form a connected graph?

On another subject, if a group has finite exponent, then the chromatic number of its power graph is finite; but the proof uses the Axiom of Choice. Is there a model of ZF set theory in which the power graph of an abelian group of exponent 3 cannot be coloured with three colours? (The existence of such a colouring requires us to choose one of each inverse pair of elements of such a group.)

And finally, we prove in the paper that, if three elements of a group have the property that any two generate a cyclic group, then the group generated by all three is cyclic. It seemed to us that this should already be known; but we were unable to find a reference. Does anyone know of one?

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