Citations briefly revisited

Sorry to return to this boring topic again; but here is an excellent example of both what is wrong with judging research by citations, and a challenge to those who would do so.

From New Scientist, 6 February 2010:

[X's] 2004 paper in Science has now been cited over 350 times by other researchers. Yet many remain sceptical. One criticism is that …

How does the journalist know this? Because the criticism is expressed in journal articles, which can be found because they cite the paper concerned. Not all citations are positive!

So, a small challenge: look at the 350 papers citing this work; how many of them are critical? If critical citations count as –1, what figure do we get?

Incidentally, two articles later in New Scientist we read:

One leading expert, on condition of anonymity, told New Scientist that the estimates were “ridiculous” and privately accused [Y] of being “more interested in getting papers into Nature and Science than in getting it right”.

Leaving aside the scurrilous personal attack under this cloak of anonymity, is there a mechanism that could explain this paradox? I think there is. Just as researchers are under pressure to publish in high-impact journals, so journals must be under pressure to publish articles that will attract more citations. A controversial article will do so, despite having a higher probability of being wrong; indeed, all the better if it inspires many researchers to refute it!

It may appear that I am saying that we shouldn’t write speculative papers. Of course I am not; merely that citation data does not reliably judge the worth of a paper without further information, which can only be obtained by reading the paper and making a judgment.

But, to close: Mathematics notoriously has lower citation rates than most of science. Probably the main reason for this is that, if I quote a theorem, I only need to cite the proof of the theorem, not to pile up experimental evidence for it. But perhaps another reason is that mathematics is relatively uncontroversial (a proof is a proof, after all), and mathematics papers don’t tend to attract negative citations.

Counting

I’m teaching enumerative combinatorics this term; it brings an old incident back to my mind.

In 1984, Dugald Macpherson and I stopped for breakfast at a Dutch pancake house near Vancouver. The restaurant offered a choice of “1001 toppings”. We speculated that, because 1001 is 14 choose 4, there were 14 different sorts of toppings, and you could choose any four. But it wasn’t so; there were 25 different sorts of toppings, and you could have any combination, giving 33554432 possibilities.

Clearly, 1001 was just meant to convey “a very big number”, possibly with shades of Scheherezade and the mystic East.

A somewhat similar thing happened here recently. McDonalds, in posters splashed all over the Underground, offered a “meal deal” with 40312 combinations. What is special about 40312? It is 8!–8, certainly, but I offer a small prize to anyone who can find a “natural” counting problem to which the answer is n!–n.

Still, this suggests that McDonalds, or their advertising department, thought that 40312 was somehow related to the number of combinations of 8 things. The discussion made the “Feedback” column of New Scientist, where somebody pointed out that in that case the number should be 255. Finally someone who shares my tastes wrote to point out that the number should be 256: “you forgot my favourite combination.”

(Another possible book topic there: “Empty Set Theory”.)

I was on the verge that we should give this sequence the name “the McDonalds
sequence” and study its properties, but it has already been done: the Encyclopedia of Integer Sequences lists it as sequence number A005096, with the following comment:

McCombinations: in 2002, McDonalds advertised a McChoice menu of 8 items under the heading “40,312 combinations” rather than the more obvious 2^8-1=255 (A000225). The Advertising Standards Authority “considered that the number quoted in the advertisement was not necessarily so exaggerated as to be misleading”. – Henry Bottomley (se16(AT)btinternet.com), May 01 2003

Another counting problem was encountered by Myles Aston, who described it in the course of a book review in the Balliol College Annual Record in 2001:

The miserable wasteland of multidimensional space was first brought home to me in one gruesome solo lunch hour in one of MIT’s sandwich shops. “Wholewheat, rye, multigrain, sourdough or bagel? Toasted, one side or two? Both halves toasted, one side or two? Butter, polyunsaturated margarine, cream cheese or hoummus? Pastrami, salami, lox, honey cured ham or Canadian bacon? Aragula, iceberg, romaine, cress or alfalfa? Swiss, American, cheddar, mozzarella, or blue? Tomato, gherkin, cucumber, onion? Wholegrain, French, English or American mustard? Ketchup, piccalilli, tabasco, soy sauce? Here or to go?”

The precise number of combinations here depends on whether you are allowed to opt for “none” in answer to any of the questions – the empty set strikes again!

My last two examples have nothing to do with eating, and I freely admit that I am recycling them from exercises in my Combinatorics book published in 1994.

According to the Buddha,

Scholars speak in sixteen ways of the state of the soul after death. They say that it has form or is formless; has and has not form, or neither has nor has not form; it is finite or infinite; or both or neither; it has one mode of consciousness or several; has limited consciousness or infinite; is happy or miserable; or both or neither.

He does go on to say that such speculation is unprofitable; but bear with me for a moment.

With logical constructs such as “has and has not form, or neither has nor has not form”, it is perhaps a little difficult to see what is going on. But, while I hesitate to disagree with the Compassionate One, I think there are more than sixteen possibilities described here: how many?

The Library of Babel, according to Jorge Luis Borges, consists of interconnecting hexagonal rooms. Each room contains twenty shelves, with thirty-five books of uniform format on each shelf. A book has four hundred and ten pages, with forty lines to a page, and eighty characters on a line, taken from an alphabet of twenty-five orthographical symbols (twenty-two letters, comma, period and space). Assuming that one copy of every possible book is kept in the library, how many rooms are there?

All mathematicians should read Borges. I am going to have to acquire at least a rudimentary knowledge of Spanish: a former student gave me a copy of Borges y la Matemática by Guillermo Martínez.

Combinatorics for the working mathematician

Irene Galstian suggested to me this week that I should write a book with the title Combinatorics for the Working Mathematician.

The title is obviously a take-off of Saunders Mac Lane’s Categories for the Working Mathematician. It is interesting to think of how such a book, if I ever get around to writing it (publishers – are you reading this? would you like to give me an advance?), would differ from Mac Lane’s. This difference is, I think, less in our writing styles and more in the nature of the two subjects.

Category theory is foundational. It is uber-Bourbaki. When I first arrived in Oxford, the first abstract algebra that the undergraduates met in their second year was category theory. Now it is not disrespectful to category theory to say that this was a pedagogical disaster. Just as you can’t philosophise until you have some knowledge to philosophise about, so category theory without a fairly detailed knowledge of the categories of groups, rings, and vector spaces makes no sense.

Indeed, like any foundational subject, category theory has a dual aspect. As Jon Barwise and Lawrence Moss said about set theory in their book Vicious Circles (about set theory without the Axiom of Foundation),

Set theory has a dual role in mathematics. In pure mathematics, it is the place where questions about infinity are studied. Although this is a fascinating study of permanent interest, it does not account for the importance of set theory in applied areas. There the importance stems from the fact that set theory provides an incredibly versatile toolbox for building mathematical models of various phenomena.

In the same way, category theory began as a technical tool in a technical part of algebraic topology, and later came to be touted as an alternative (and better) foundation for mathematics.

The point is that, in part, Mac Lane’s job was to persuade working mathematicians that category theory was a useful addition to their bag of tools, while in reality, either they knew this already, or it simply wasn’t true.

The situation with combinatorics is quite different. Like M. Jordan in Molière’s Le Bourgeois Gentilhomme, who discovered that he had been speaking in prose all his life, most mathematicians have been using combinatorics for most of their careers, probably very fluently and effectively, without beven considering that they have discovered theorems which could be written up and submitted to combinatorics journals. In the introduction to Roger Lyndon’s collected works, Kenneth Appel (one of the editors) write,

Lyndon produces elegant mathematics and thinks in terms of broad and deep ideas … I once asked him whether there was a common thread to the diverse work in so many different fields of mathematics, he replied that he felt the problems on which he had worked had all been combinatorial in nature.

Because everybody does it, it is not highly regarded. I was in the audience when Anthony Joseph said in a lecture,

These results, which are partly combinatorial and partly real mathematics …

Henry Whitehead famously said, “Combinatorics is the slums of topology”. He presumably meant that a graph is a 1-dimensional simplicial complex, but notice how this statement avoids the derogatory tone of Whitehead’s. (It is fair to add that this statement has been attributed to other mathematicians; I base the attribution to Whitehead on a statement by Graham Higman, a student of Whitehead.)

Along with disparagement is incomprehension, the thought “Is this really mathematics?” which comes through Joseph’s statement. Here is Jean Dieudonné giving what might be the view of Bourbaki:

We have not begun to understand the relationship between combinatorics and conceptual mathematics.

The aim of the book, were I to write it, would simply be to say, “If, like so many mathematicians, you have to use combinatorial techniques in your work, you may be interested in a survey of the techniques that are available.” This feels like the right way to go. Tim Gowers, in a perceptive article on “The two cultures of mathematics”, distinguished between parts of mathematics which are about big theorems, and parts which are more concerned with technique, including graph theory in the latter:

It is obvious that mathematics needs both sorts of mathematicians [theory-builders and problem-solvers] … It is equally obvious that different branches of mathematics require different aptitudes. In some, such as algebraic number theory, or the cluster of subjects now known simply as Geometry, it seems … to be important for many reasons to build up a considerable expertise and knowledge of the work that other mathematicians are doing, as progress is often the result of clever combinations of a wide range of existing results. Moreover, if one selects a problem, works on it in isolation for a few years and finally solves it, there is a danger, unless the problem is very famous, that it will no longer be regarded as all that significant.

At the other end of the spectrum is, for example, graph theory, where the basic object, a graph, can be immediately comprehended. One will not get anywhere in graph theory by sitting in an armchair and trying to understand graphs better. Neither is it particularly necessary to read much of the literature before tackling a problem: it is of course helpful to be aware of some of the most important techniques, but the interesting problems tend to be open precisely because the established techniques cannot easily be applied.

Here is a small example. Enumerative combinatorics makes use of formal power series to wrap up an infinite sequence of counting numbers (such as the number of trees with n vertices, for n=1,2,…) into a single mathematical object. In fortunate circumstances, the power series converges in some domain of the complex plane, and defines an analytic function there. Now complex analysis has much to say about analytic functions in circular domains centred at the origin; but combinatorics has a single concern: can we extract useful information about the coefficients (ideally a formula, but at least the asymptotics)? So combinatorial enumerators read complex analysis very selectively, and extract results like Hayman’s Theorem, or the theorem of Bender on implicitly defined functions.

Who is deluded?

On my way to lecture yesterday, I passed a poster by the Islamic Society advertising a talk with the nice snappy title “The Dawkins Delusion”.

Unfortunately, coming as it did at the end of a month in which hundreds of Muslims have been killed by Christians in Nigeria, and seven Christian churches firebombed by Muslims in Malaysia (both formerly more tolerant places), I couldn’t help seeing Dawkins as a model of clear thinking by comparison.

Open University Winter Combinatorics Meeting

Everybody needs ritual. For combinatorial mathematicians in Britain, certain times of year mean one-day conferences. For many years, mid-May brought a welcome break from exam marking, and a day out in Reading, where the buttercups were in full bloom and waterfowl chicks swam in the lake. But no more. Richard Rado and Crispin Nash-Williams are dead, David Daykin has retired, and Anthony Hilton was forced out by the University’s decision that pure mathematics is no longer part of their mission.

The longest-running one-day combinatorics conference series is now the winter meeting at the Open University; that is where I was last Wednesday.

Someone told me once “Bletchley used to be where you change trains travelling between the two English universities; now it has two universities of its own.” One of these (a campus of De Montfort) has closed its doors; but the Open University is still in business. Of course, Bletchley has become part of Milton Keynes New Town. It is a strange town, built on a non-Euclidean grid of H and V roads, where two H roads intersect at right angles at some mythical spot; it is best known for its concrete cows, which have given their name to a local brewery (I have seen them, but not on this trip).

The strangeness extends to the university, which is full of academics and administrators but has virtually no students, although in terms of student numbers it is the largest in Britain by a big margin. (The university’s business is distance learning.)

A train and taxi got me to the university in good time (though the taxi cost me more than the return train fare). But then the troubles started. There is a lot of rebuilding work, so everything looked different; and the doors are on card access, so I had to slip in when someone came out. I got to the common room just as everyone was starting the long trek to the lecture room.

At lunch, after a sandwich,I suggested a walk; two students came with me. We went along the river Ouzel (in spate, after recent rain and snow), and through the deserted mediaeval village of Woughton, then back on the other side of the river. Birds were singing, but not showing themselves.

What was there in the way of nice mathematics?

Lowell Beineke, aka Mr Line Graphs, talked about some generalisations of line graphs. He made a brief reference to Alan Hoffman’s work, which I have touched on in an earlier post. He ended with a little puzzle, which must surely be not too hard. Given two integers m and n, what is the maximum value of min(ac,bd), over all a,b,c,d with a+b=m and c+d=n? If m and n are even, the best we can do is to take a=b=m/2 and c=d=n/2. Otherwise, splitting nearly equally is not always best; for example, if m=13 and n=29, then min(6.15,7.14)=90 is beaten by min(6.16,7.13)=91.

Lesley Goldberg gave a nice talk about stable matchings. The setup is usually explained in terms of n men and n women, each of whom has arranged the people of the opposite gender in order of preference as partners. A matching between men and women is stable if there does not exist a man M and woman W, not paired with each other, who each prefer the other to their current partner. Gale and Shapley showed that, for any preference lists, a stable matching exists. But it is hard to count exactly how many there are. Lesley’s talk was about approximating this number, which is similar in difficulty to approximating the number of independent sets in a bipartite graph.

Dan Archdeacon talked about a variant of Conway’s thrackle conjecture. A graph can be thrackled if it can be drawn in the plane in such a way that no edge crosses itself, adjacent edges don’t cross, but non-adjacent edges cross once. He conjectured that a graph which can be thrackled has at most as many edges as vertices; this is still open. Dan said that a graph is superthrackled if any two edges cross once. He can describe such graphs completely. Surprisingly (or not, given his interests), it depends on embeddings (without crossings) of graphs in other surfaces. There was also a puzzle: their class of graphs is identical with the class having a “generalised thrackle”, though there is no obvious reason why the concepts are equivalent.

Anything else? Well, the trains were late (five minutes going out; half an hour coming home).

An early birthday present

I am not very much in tune with the modern world. No car, television, microwave, tumble dryer, not even a mobile phone. But I did have one very useful gadget for many years: the late lamented Psion Organiser.

This lovely gadget was small enough to fit into a shirt pocket, and yet came with a suite of easy-to-use but powerful programs: word processor, agenda, database, spreadsheet, and so on. No booting up; turn it off when you have finished, and when you turn it on again you will be back exactly where you left it. Best of all, it ran for 40 hours on a pair of AA batteries.

Among other things I used it for, I produced most of a book on a single crossing from Hoek van Holland to Harwich on the North Sea Ferry. I had given a course at the Euler Institute in Eindhoven, and at the students’ request had produced written lecture notes. I typed up the notes on my Psion on the ferry. That was the bulk of the work, though I did later add one more chapter and did some editing. That book, Permutation Groups, is the best I have done.

The Psion had two weaknesses. First was connectivity: before the advent of USB, it talked to other computers over a serial line, and anyone my age will know what a black art those things were. A third-party manufacturer produced a disc drive for it, which was fine until computers stopped having disc drives. I did manage to keep going by getting a serial-to-USB converter, but it was necessary to say the right spells before firing it up.

The other problem was that the company making Psions abandoned them and went into mobile phones, so I was very exposed to the chance of a malfunction, which happened from time to time. A wonderful organisation, Pinnock Organiser Services, patched up various Psions of mine. But at a certain point, I could see that the end was nigh.

That point happened to be at the beginning of 2008, just when Asus brought out their first netbook, the EEE-PC. Though it was several times larger than the Psion (and would certainly not fit in my pocket), and made for children, it ran Xandros Linux; once I had found from a user web-page how to get a terminal (Ctrl-Alt-T, if you need to know), I could happily use it for writing. No diary program, but I could at least keep a diary as a plain text file. It saved my bacon several times, especially in New Zealand, as told in my Forder diary.

But this year, a week before my birthday, great-granddaughter of Psion is a reality: the psiXpda, a real computer, running Ubuntu Linux. You can have Windows XP, if you must, but can you really pass up an operating system named after a concept defined like this by Archbishop Desmond Tutu, no less?

A person with ubuntu is open and available to others, affirming of others, does not feel threatened that others are able and good, for he or she has a proper self-assurance that comes from knowing that he or she belongs in a greater whole and is diminished when others are humiliated or diminished, when others are tortured or oppressed.

It is almost exactly the size of the Psion (that is, pocket-size). It has a rechargeable battery lasting for five hours, a gigabyte of RAM and 16 Gigabytes of SSD memory, USB, mini-USB, and micro-SD slots. I am typing this on my new machine.

Positive things: the screen is astonishingly good (a page of 12-point text, rotated, is readable, while pictures are a delight); it comes with goodies like GIMP (and the screen is good enough that simple image manipulation is quite feasible); it has Bluetooth and wi-fi (I haven’t tested these yet); you can listen to music while you work (the music degrades the response a bit but not too badly).

On the negative side: the keys are very stiff and noisy, so it is not a joy to type on; the position of the screen when tilted up makes the top row of keys tricky to access; the relatively small screen height creates problems with fixed-size windows (I have been unable to set up Evolution since the buttons to click fall off the bottom); and I miss the simple but powerful agenda program on the Psion.

I think it will become as indispensible to me as the Psion was; but time will tell.

10000 hits

I put a counter on my web page last February. Today, in just less than a year, it has reached 10000 hits. I thought this was maybe worthy of note. It doesn’t put me in the celebrity class (thankfully!), but it’s probably reasonably good for an ordinary mathematician, and shows that some people appreciate the effort I put in.

Like most academic web pages, it began as links to the course material for the courses I teach, access to my preprints, and professional affiliations. But it has grown since then; if you haven’t visited it, let me see if I can tempt you.

• I keep a list of conferences in discrete mathematics and related areas (algebra, logic, etc.). Probably this is the most visited item on the site.
• Nowadays, when I give a course, I produce a set of lecture notes as I go along, and put it on the web. I know that these notes are used in various places. Recently, Morteza Mohammed-Noori sent me a list of misprints in my Notes on Counting that he and his students had found when he gave a course in Tehran using the notes.
• My most time-consuming passion these days is walking. I started keeping a list of long-distance trails I had started or completed. At some point I decided to put the list on the web. I take photographs on my walks, and I decided to put some of these on the web too.
• An advantage of being a mathematician is that I have travelled a lot. On some of these trips I kept diaries, and some of these are now on the web. Take a trip to New Zealand, India, Iran, Slovenia, …, or Birmingham.
• There is an open problem on my web page, which changes from time to time; I keep a file of old problems with their status. You might find a research topic there.

One of the most interesting and thought-provoking blogs I have found is that of Diamond Geezer. Recently he made an amusing post where he made hay out of some corporate person who had (politely) asked him to change the wording of a year-old post. Among many good points, DG made one which is perhaps more questionable: old web-pages are an item of record and should not be altered. That got me thinking.

I agree that weblogs should not be changed. As the name suggests, they are items of record; nobody reads old blogs unless brought there as the result of a search. But there are other sorts of web pages, such as my conference listings, whose usefulness depends on their being updated regularly. And as always in life, when you distinguish two categories of things, you find that there are many cases that don’t quite fit the pattern. Anyway, my webpage carries a notice “The contents may change at any time”. I think it is these changes that bring my visitors back.

In a couple of years, I will be pensioned off, and sent to the old men’s room in the sky (strictly speaking, on the fifth floor, with views of Tower Bridge and Limehouse). Probably my webpage will disappear at that point. So read it while you have time!

Excellent teaching?

Next month, a fairly new event in the British academic season opens: the National Student Survey.

Of course, there is nothing wrong with having a survey and letting students, sorry, “customers of higher education”, have their say. The problems arise in the use to which the results are put. This new survey has quickly found its way into league tables of universities published in the press. As a result, university administrators have become convinced that their goal is to improve the performance of their institutions in the survey. The problem is that they cannot dictate to the students what they should say, so all they can try to do is increase participation and engender a warm cuddly feeling.

(Please add your comments about what you think the purpose of a university is. I’ll probably get on to this topic one of these days.)

The first strategy is a recipe for disaster. If not many students from our department take part, we are in trouble over low participation rates. So we try to get them to do so, by a combination of positive and negative bribery (positive: entry in a prize draw; negative: “Your degree will be devalued if we don’t do well in the league tables”). Inevitably, it is the students who feel they have a grievance who are most likely to take part, so our satisfaction score goes down as our participation rate rises, and we are in trouble again.

The second aspect, the desire to give the students a warm feeling about us, led to something I never thought I’d see, which deeply shocked me. This week, our Director of Undergraduate Studies told us that we should not teach too well (or too badly): if we do, then students will notice the gap between the best and the worst teachers and this will cause feelings of dissatisfaction. We should all aim to be equally mediocre. I think he was looking at me when he said this, since I won a teaching award a few years ago. I alluded to this in a previous post, but now I think the time has come to tell the story. (I will have to suspend my natural modesty to do so, if I can.)

As I explained in the earlier post, I was nominated for a Drapers Company teaching prize by some of the students. I received an email from someone in registry, quoting what the students said about my teaching, for example

Professor Peter Cameron is a truly inspirational figure among both the students and faculty staff. He is not only always willing to answer any queries, but he can do so in many ways with equal enthusiasm until the student is left satisfied. His love of his mathematics is infectious and mixed with his benevolent composure makes him the perfect candidate to win this prize.

The letter invited me to submit a “teaching statement” and CV.

After some deliberation I decided to give it a go. I don’t suppose anyone now wants to read my teaching statement, but I will summarise it; these are things I do feel strongly about.

I was invited to discuss my “innovations” in teaching. I explained that the most important of these was to write everything on a blackboard with a piece of chalk. This has several advantages: it slows me down to a rate that the students can follow (unlike OHP or data projector which encourage you to go much too fast); it enables the students to take complete notes which should make sense on re-reading; and it lets me change the flow of the lecture in mid-stream if I see that the students are not following, or if questions lead us in a different direction.

At the same time, I use modern technology by putting good notes on the web after the lecture, so students get a second chance to see what they maybe didn’t catch first time around. I make these notes as good as I can, and keep them on the web even after I stop teaching the course. I know that people all over the world use them.

Another thing I do which is very popular is to have a liberal policy towards students who come to my office to ask questions. Before my present position, I was an Oxford tutor for eleven years; this meant that I had to acquire a very good knowledge of a wide range of mathematics. Students learn that I may be able to help them on many of their courses, from analysis to statistics, even if I am not teaching these courses. They really appreciate this, and the nominations referred to this. I think it was what our DUGS was specifically condemning last Monday.

And here, gratis, is a blast against those people who think that teaching and research are mutually exclusive, and we should specialise in one or the other. The breadth of view I gained teaching in Oxford has been very important in making me the kind of researcher I am, one who takes more pleasure in making unexpected connections than in digging deep. The citation data on my papers “demonstrate” (so far as such data can show anything) that those which make connections are the most important.

I also put in something about course design. Two recent courses I have designed are Cryptography (a popular topic, and something students like to have on their CVs), and first-year Introduction to Algebra(something of a challenge for me since some of my colleagues didn’t think you could teach abstract algebra to first-year students any more – well, you can, and they will rise to the challenge of learning it, I am glad to report.)

Anyway, the administrative wheels ground on, and they decided to award me the prize.

It was presented at the graduation ceremony that year. We have several ceremonies since the Great Hall is not great enough to hold all our graduands. I got the prize at the Mathematics students’ graduation. The vice-principal for our sector read the citation, and the vice-principal for teaching and learning (who was presiding in the principal’s absence) presented me with the certificate.

And then an extraordinary and moving thing happened. The graduating mathematics students rose to their feet and gave me a standing ovation. I have never had an experience like it. The presiding vice-principal had never seen anything like it either; this sort of thing doesn’t happen in the formal surroudings of a degree ceremony! It pleased me partly because I knew she had read my submission, and I thought that a valuable message about what constitutes good teaching in mathematics might have been sent.

It is a cliché, but no less true for that, that a good teacher can have a big effect on your life; I know this from my own experience. Nothing would give me more satisfaction than to have such an effect on one of my students. The NSS notwithstanding, mediocre teaching is not likely to have this inspirational effect. So I will ignore that particular bit of stupidity and continue to do the best I can.

Graphs and groups

Last week I gave a short talk at the London Taught Course Centre open day. The LTCC is an organisation run by a consortium of universities and colleges in the London area, putting on courses for PhD students to broaden their mathematical background. The purpose of the open day was to help undergraduates or Masters students thinking of doing a PhD by putting a variety of options (subjects and institutions) before them.

I decided that, rather than advertise my subject or my institution, I would try to give an example of research, by talking about a recent result of mine. I had 30 minutes scheduled, but because of the severe weather the programme was curtailed and I had to compress it into just 20 minutes. Not much time for the purpose.

Here is a summary. More details should be available on the LTCC website.

Groups are very highly structured algebraic objects, while graphs are much looser. For example, there are just five different groups with eight elements, but 12346 different 8-vertex graphs. But the two subjects have various points of contact. For example, any graph has an automorphism group; and indeed several of the sporadic finite simple groups were constructed as automorphism groups of interesting graphs.

My talk was about the reverse direction. Given a group, construct a graph from it, which captures some information about the group. There are several ways of doing this, but the particular one I discussed is the power graph of the group. This comes in undirected and directed versions. I learned about it last summer at the British Combinatorial Conference when Shamik Ghosh from Kolkata asked a question about it.

The power graph comes in two versions. The directed power graph of G has the elements of G as vertices, with a directed edge from b to a if a is a power of b. The undirected power graph is obtained simply by ignoring the directions; in other words, a and b are joined by an undirected edge if one is a power of the other.

It is clear that the directed power graph carries much more information about the group. It is a preorder (a reflexive and transitive relation) on the group. From a preorder, we derive an equivalence relation (two elements are equivalent if there are directed edges in both directions between them – here, this means that they generate the same cyclic subgroup), and a partial order on the set of equivalence classes. In a finite group, the identity is the unique minimal element (it is a power of everything), and the elements that cover it are elements of prime order; the prime p in question is determined by the fact that the size of the equivalence class is p–1. From this it is possible to work out the orders of all elements. In other words, the directed power graph tells us the number of elements of each order in the group.

Shamik Ghosh’s question became, after some discussion, the following:

If two finite abelian groups have isomorphic undirected power graphs, must the groups themselves be isomorphic?

(Both conditions “finite” and “abelian” here are necessary.) After some email exchanges, we had the proof, and had written a paper.

At the start of last term, I gave a talk about this, and offered to buy a drink for anyone in the audience who could answer the following question:

If two finite groups have isomorphic undirected power graphs, must they have the same number of elements of each order?

Shamik’s and my proof for abelian groups had first shown that two such groups must have the same number of elements of each order. For abelian groups, this information determines the group completely.

But nobody took up the challenge, except for my colleague John Bray, who made a first step, and I had to do the work myself. To my surprise, the final result was the following, beautifully clean, theorem:

If two finite groups have isomorphic undirected power graphs, then they have isomorphic directed power graphs.

In other words, contrary to our previous intuition, the undirected and the directed power graph of a finite group carry exactly the same information!

Of course, this settles the above question (so I had to buy myself that drink), and implies the theorem that Shamik and I had proved earlier.

As always in research, a result like this raises many more questions than it settles. Here, briefly, are a few.

• Given a (directed or undirected) graph, how do we tell whether it is the power graph of a group? What is the computational complexity of deciding this?
• What can be said about the number of groups of order n which are not determined by their power graphs, or the maximum number of non-isomorphic groups of order n which have isomorphic power graphs?
• Can “natural” graph-theoretic properties of the power graph of G, such as chromatic number, be related to “natural” group-theoretic properties of G?
• What is special about groups? Does the theorem hold more generally, e.g. for classes of semigroups or loops?
• For infinite groups, what extra information do we need to distinguish groups with the same undirected power graph but different directed power graphs?
• What about other graphs defined from groups?

Who knows; a successful assault on one of these might be the start of a PhD and a career as a mathematician.

Typography

One of the first, and most successful, examples of corporate identity was the commissioning and use of a sans serif typeface from Edward Johnston by Frank Pick for the London Underground in 1913. Johnston was an highly original and influential type designer, who taught Eric Gill (and Gill Sans bears more than a passing resemblance to Johnston Sans). This typeface is ideal for purpose, which is for signage: it is easy to read station names and “Way Out” signs even in the poor light of the underground. The typeface was re-designed by the Japanese type designer Eiichi Kono, with extra symbols added, and is used for information posters by the Underground now. The redesign, in my opinion, keeps the spirit of the original very well. A splendid account of the history of this typeface can be found here on the London Reconnections blog.

In 2007, I was nominated by some students for one of the Teaching Prizes given by the Drapers’ Company. I was informed of the nomination by someone in the College registry, who, after congratulating me on the nomination and quoting what the students said about my teaching, went on to invite me to submit a teaching statement in 11-point Arial(sic), with widths of top, bottom and side margins specified to three significant figures (specifically, “2.54cm margins left and right and 3.17cm margins top and bottom” – I invite you to convert these to Imperial units!). I was sufficiently upset that I seriously considered ignoring the invitation. In the end, I wrote something, and set it in Palatino, with the correct margins – I do not have Arial available, not being a user of Microsoft products. What happened next is interesting, and perhaps I will tell it later; but suffice to say here that my statement was not rejected on the grounds of typeface.

Perhaps I would not be so lucky another time. I understand that the College now requires the use of Arial in all its documentation. The reason is an interesting example of how the tail wags the dog nowadays. Apparently some survey (I cannot give documentation since nobody has been able to point me to the source) showed that a certain group of dyslexic students are confused by serifs on letters. (This is still no good reason for using Arial rather than a better sans serif face, but let that pass.) I believe I would have no difficulty in pointing to research showing that serifs actually aid readability for the majority of us, especially in body text. Sans serif fonts are ideal for station names but turgid 40-page policy documents are slightly less indigestible in a serif font. Indeed, Times Roman is widely recognised as the most easily readable font.

Mathematics, as in so many things, is a special case. Mathematicians need a wide variety of symbols in their writing. It is not uncommon to use the same letter in several different cases with different meanings in the same document.

When I was a student, I spent some time reading papers of Richard Brauer. For him, 𝔊 (your browser probably can’t read that – mine can’t – it is Fraktur capital G) was a finite group; its order was italic lower case g, while italic capital G was a typical element of the group. Apart from the fact that I couldn’t tell the Fraktur capital letters apart (I still have trouble with this), I found this confusing because conventions have changed: now G is a group and g one of its elements, and its order, if we need it, is probably n. Worse is to be found by going back further. Sylow, in the paper proving the most important theorem about finite groups, used n for a typical prime number, and p for the part of the group order not divisible by n.

(By the way, I frequently write or lecture about graphs and groups. Both graph theorists and group theorists like to denote their objects of study by G, so I have to upset at least one camp. I reckon that, since “graph” is a Greek word and “group” a German, the logical approach would be to write Γ (Greek capital Gamma) for a graph and 𝔊 (Fraktur capital G) for a group. But I am afraid I am incompetent at writing Fraktur letters on the blackboard, so my groups remain as G.)

The point is that reading mathematics is hard enough, it is important that the typesetting should help you rather than distracting you!

In any discussion of typesetting, the mathematician in the company will always look smug. The reason is that, for about 40 years, we have been the beneficiaries of Donald Knuth, a mathematician turned computer scientist and pioneer of computerised typesetting, who devised the wonderful system TeX (pronounced “tech”: the program name τεχ (tau epsilon chi) is made up of the first three letters of the Greek word “techne”, which combines the senses of “technology” and “art”. For mathematical typesetting is an art. In the 1990s, the last time I had any experience with Microsoft Word, it allowed you to include a mathematical formula in a document by selecting symbols from a menu and placing them by trial and error until you had something looking approximately correct; then you would find that the printout looked quite different from what you had on the screen. TeX, on the other hand, took the rules evolved by hot-metal typesetters over many decades for spacing (a bit more space around a relation like = than around an operation like +, for example – I wish I knew how to do that nicely in HTML), shrinking size of subscripts, and so on, and built them in. The result meant that an ordinary mathematician could produce work comparable to that of a professional typesetter. Also the output was device-independent, to the limit of resolution of the device (screen, printer, typesetting machine).

Knuth also designed fonts to go with TeX, with the mathematical symbols carefully matched to the letter forms. His Computer Modern fonts were not to everyone’s taste (“modern” here is a technical term, referring to fonts such as Bodoni which were developed in the eighteenth century, lighter in weight than the earlier “old-style” fonts); but there is no doubt that his aim, of enabling us to produce beautiful books, especially books containing some mathematics, was realised. Now, it is completely straightforward to use, say, Times Roman or Palatino instead of Computer Modern (though the symbols are not integrated as successfully with the letters in either of these). Finally, he gave the copyright to the American Mathematical Society.

We need all possible clues, including familiarity with the typeface, consistent design of symbols, and serifs, to distinguish letters. I fear the day when the College tries to force us to set our exam papers in Arial. Hopefully I will have retired before this happens! Since we all produce course material using TeX, students get to know what proper printed mathematics looks like. Changing the system for the exam would seriously disadvantage everybody, even (I believe) the students it is designed to help.