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.