Notes on Counting

Notes on Counting

My book Notes on Counting: An Introduction to Enumerative Combinatorics should be published by Cambridge University Press in June this year, as part of the Australian Mathematical Society Lecture Series.

If you have read some of my lecture notes on enumerative combinatorics, you may want to know that this book contains more than just the union of all the notes I have written on this subject!

If you are interested, there is a flyer, and preorder form, here.

But no job is ever finished. In the book, at the start of Chapter 4, I prove (as an introductory example for recurrence relations) that the number of compositions of n (ordered sequences of positive integers with sum n) is 2n−1 if n ≥ 1. The easy proof involves showing that the number of compositions of n is twice the number of compositions of n−1. When I came to mark my St Andrews exam, I found that two students had produced a beautifully short and elegant proof of this, which may not be new but was certainly new to me!

It goes like this. Imagine you are a typesetter; you set up a row of 2n−1 boxes, each to contain a symbol. In the odd numbered boxes you put a 1; in the even numbered boxes, you choose to put a plus sign or a comma. Your 2n−1 choices give all the compositions of n, each once.

For example, the compositions of 3 are

1+1+1    1+1,1    1,1+1    1,1,1

Posted in books, exposition | Tagged , | 4 Comments

London Combinatorics Colloquia 2017

A brief trip to London for the two colloquia and a meeting of the committee, marred for me by the fact that I had come down with quite a bad cold (which, scarily, involved my losing my balance from time to time).

What follows are random musings on what we heard in a very enjoyable two days.

Three speakers mentioned Galton–Watson branching processes in similar contexts: Andrew Treglown, Oliver Riordan and Guillem Perarnau. I got two insights from this, which I had probably not realised clearly before. First, Erdős–Rényi random graph is the same thing as percolation on the complete graph. (For percolation on a graph, we allow edges to be open independently with probability p and ask questions about whether the resulting graph has a “giant component” and similar things. Erdős and Rényi simply included edges with probability p from all 2-subsets of the vertex set, and asked similar questions.)

Secondly, for percolation in any regular graph of valency d, to explore the component containing v you look at the neighbours of v, their neighbours, and so on until you have seen everything. The number of neighbours of any vertex (apart from the vertex on the path from v by which we reached it) is a binomial random variable Bin(d−1,p), and the whole process is “stochastically dominated” by the Galton–Watson process with this rule for descendents. (In an infinite tree, they would be identical; but the possibility of short cycles means that we will not see more vertices in the percolation case than in the Galton–Watson case.)

The three speakers tackled different problems. Perarnau was looing through the critical window in the percolation problem for regular graphs. Treglown was examining resilience of random regular graphs, e.g. how many edges can you delete before losing the typical value of a Ramsey number in the graph. (As he said, there are two processes going on here: first choose a random graph, then delete an arbitrary subset of its edges.) Riordan was considering the Achlioptas process, a variant on Erdős–Rényi where, at each step, you choose two random edges, and keep one, the choice depending on the size of the components they connect.

Kitty Meeks talked about complexity problems for sum-free sets. How do such problems arise? She began with a theorem of Erdős, according to which any set of n natural numbers contains a sum-free subset of size at least n/3. Now one can ask whether there is a sum-free subset of size n/3+k, or to count such subsets. This kind of problem lends itself very well to analysis via parameterised complexity.

Sophie Huczynska talked about the “homomorphic image” order on relational structures such as graphs: in this order, G is smaller than H if there is a homomorphism from G to H mapping the edge set of G onto the edge set of H. (She began by describing a variety of graph orders, such as subgraph order, induced subgraph order, and minor order, and showing how all can be expressed in terms of homomorphisms.) Typical questions are whether a class of graphs or other structures is a partial well-order with respect to the homomorphic image order (that is, whether it contains no infinite antichains), and describing the antichains if possible.

A special mention for Ewan Davies, who stepped in at very short notice when Agelos Georgakopoulos was unable to speak. (We found out the reason later; his wife had produced their first son that very day.) Evan gave a fascinating talk on getting accurate values or estimates for the coefficients of the matching polynomial of a graph (the polynomial in which the coefficient of xk is the number of matchings with k edges in the graph), using ideas from statistical mechanics. (The matching polynomial is the partition function for the monomer-dimer model on the graph.) There was even some differentation! A very assured and confident talk which raised lots of questions from the audience.

I am afraid I didn’t feel up to having drinks afterwards, so just sneaked off home.

Posted in events | Tagged , , , , , , | 1 Comment

Laszlo Babai in St Andrews

I promised to say a few words about Laci Babai’s visit to St Andrews. In an amazing performance, he gave five talks: one of nominally an hour at the Scottish Combinatorics Meeting (it was actually the last talk of the meeting, and had to be cut slightly so people could leave), two ninety-minute tutorials on the proof of his quasi-polynomial bound for graph isomorphism, and two talks to the undergraduate mathematics and computer science societies.

I don’t intend to give a blow-by-blow account of all this.

The big theorem says that there is an algorithm which tests isomorphism of two n-vertex graphs in time bounded by exp(O(log n)c) for some constant c. As the name might suggest, the bound is polynomial if the constant c is equal to 1. The best previous result for graph isomorphism was exp(O(nc)), that is, fractional exponential.

The strategy is “divide and conquer”, and as Laci explained, his job was to divide, since the conquering had already been achieved by Luks. The dividing is rather involved, and I won’t attempt to describe it. Any graph isomorphism algorithm has to name an object in the graph; this incurs a multiplicative cost equal to the number of objects which could have been named.

The basic division step is called “split or Johnson”. It identifies, at a cost which can be controlled, either a small subset of the vertex set, or a partition of the vertex set, or a Johnson graph (whose vertices are the k-element subsets of an auxiliary m-element set). But for the induction, we have to have the structure of a graph on the auxiliary set, and further complicated reductions were needed to achieve this.

In the second tutorial, he described carefully the mistake that Harald Helfgott had found in the proof, and how he had fixed it. The arguments seemed fairly familiar to me; there are similar things in my Oxford DPhil thesis in 1971. This was the time when the graph-theoretic methods introduced into permutation group theory by Charles Sims and Donald Higman were beginning to make their mark on permutation group theory.

Nothing is ever lost!

Posted in Uncategorized | Leave a comment

Mathematical diversity

Don’t worry, this post is not about factors irrelevant to mathematics such as gender, ethnicity and sexual orientation.

Nor is it about important factors, highlighted in the 2011 International Review of UK Mathematics although largely ignored by the research council that commissioned it: research area, size of research group, and size of institution.

But I discovered recently a diversity in the way we do mathematics, which I found surprising and potentially significant.

A few weeks ago, I was at dinner with a visiting colloquium speaker. The conversation turned to whether mathematical thought is done in words, or is “pre-linguistic”.

This is a topic about which Jacques Hadamard, in his book originally called The Psychology of Invention in the Mathematical Field but re-published as The Mathematician’s Mind, had a lot to say. Some linguists and linguistic philosophers, notably Max Müller, insist that language is essential to thought, and that no thoughts can be pre-linguistic. Hadamard, from his own intuition and from the writings of others from Poincaré to Einstein, is convinved that this is not the case, and is bewildered that Müller can hold this view with such vehemence. In a footnote, he says,

I have also seen the following topic (a deplorable subject, as far as I can judge) proposed for an examination—an elementary one, the “baccalauréat”—in philosophy in Paris: “To show that language is as necessary for us to think as it is to communicate our thoughts.”

For me, I know for sure that my best insights (those which are not just routine calculations) are pre-linguistic, and I struggle to put them into words: similarly, if the insight is a conjecture, I struggle to see how the conjecture might be proved. I assumed that most mathematicians would be like me, and would agree with Hadamard rather than Müller.

So it was a bit of a surprise when, of the five research mathematicians at the table, we were split 3 to 2 in Hadamard’s favour.

This is of course an anecdote, and not survey data. But we noticed a curious thing. The two who said they did mathematics in words had something probably significant in common: their cradle tongue (in both cases, a Slavic language) was not the language in which they do mathematics (in both cases, English); and both of them had learnt English at a comparatively advanced age. The other three of us were all native English speakers.

Not sure what to make of this. But I am glad that it drove me back to Hadamard’s book. I had completely forgotten that, at a certain point, he admits to his failure to be able to think creatively about group theory!

Posted in doing mathematics | Tagged , , , | 6 Comments

Power graphs of torsion-free groups

Today a paper on this topic appeared on the arXiv. I will say a bit about its contents, and how it came about.

The power graph of a group G has vertex set G, with an edge from x to y if one is a power of the other; the directed power graph is a directed graph with an arc from x to y if y is a power of x. Various studies have looked at the properties of these graphs as graphs. But the questions discussed here are:

  • If two groups have isomorphic power graphs, do they have isomorphic directed power graphs? Further, is it true that any isomorphism between power graphs is an isomorphism between directed power graphs?
  • What does the power graph tell us about the group? In particular, if two groups have isomorphic (directed) power graphs, must they be isomorphic?
  • As you would expect, all these questions have negative answers in general.

    For finite groups, it is known that the power graph determines the directed power graph up to isomorphism. But it does not determine it uniquely. (In the cyclic group of order 6, the identity and the two generators are all joined to everything, and so the power graph does not determine which element is the identity; the directed power graph clearly does.) The power graph does not determine the group up to isomorphism: for example, any group of exponent 3 has power graph consisting of a number of triangles with a common vertex.

    For infinite groups, things are worse. The Prüfer group Zp (the group of rationals with p-power denominators modulo the group of integers, where p is prime) has the property that its power graph is complete, so we cannot even determine the prime, whereas clearly we can determine p from the directed power graph.

    It seems to be the fact that all elements have finite order that causes the trouble here. So let us banish them, and assume that the group is torsion-free. These groups have the great advantage that, if x = yn, then n is unique, and moreover it cannot happen that also y = xm unless m = n = ±1.

    At once a small problem of definition arises. The identity element is equal to x0 for any element x, so is joined to everything in the power graph. In particular, in the infinite cyclic group, we cannot distinguish the identity from the two generators (much as happens for the cyclic group of order 6 in our earlier example). But, in any other torsion-free group, the identity is the only vertex joined to everything. So, if we change the definition slightly so that edges or arcs are not put in from x to x0, then the identity becomes isolated in any torsion-free group (and only in such groups), and apart from the infinite cyclic group the answers to our questions will not be changed. So we simplify things slightly by making this change.

    Now here are some of the results.

    • If the power graph of H is isomorphic to that of the infinite cyclic group Z, then H is isomorphic to Z, and any power graph isomorphism is a directed power graph isomorphism. [It need not be a group isomorphism, since an element and its inverse have the same neighbours, and so may be interchanged by a graph isomorphism.]
    • If two torsion-free nilpotent groups of class (at most) 2 have isomorphic power graphs, then they have isomorphic directed power graphs.
    • If G is a torsion-free group in which any non-identity element lies in a unique maximal cyclic subgroup (free and free abelian groups are examples of this), then the power graph of G is a disjoint union of connected components, each isomorphic to the power graph of Z with the identity removed, together with one isolated vertex. In particular, if two groups with these properties have the same cardinality, and neither is Z, then they have isomorphic power graphs; and any power graph isomorphism is a directed power graph isomorphism.

    There are also some results about Q, the additive group of rationals, and some of its subgroups. For Q we have the interesting property that any power graph isomorphism is either an isomorphism or an anti-isomorphism (reversing all directions) of the directed power graph.

    The main authors of this paper are St Andrews undergraduates Horacio Guerra and Šimon Jurina, who proved these results as part of their summer research project last year. On Wednesday they took time out from exam revision to present these results in our Algebra and Combinatorics seminar. I wish them good fortune in their exams and in their subsequent careers.

    Posted in exposition | Tagged , , | Leave a comment

    A small fact about the Petersen graph

    The Petersen graph has 10 vertices and 15 edges, and the complete graph on 10 vertices has 45 edges. However, Allen Schwenk and (independently) O. P. Lossers (Jack van Lint’s problem-solving seminar in Eindhoven) showed that you can’t partition the edges of the complete graph into three Petersen graphs; you can pack two Petersen graphs edge-disjointly, but not three.

    I described this here, and went on to explain how Sebi Cioaba and I showed that for any m ≥ 2 it is possible to cover the edges of the complete graph m times with 3m Petersens. In particular, you can cover the edges twice with six Petersen graphs.

    This means that five Petersen graphs suffice to cover the edges of the complete graph, since we may omit one of the six. We cannot, however, omit two, since any two have edges in common.

    So the minimum number of Petersen graphs required to cover all the edges is either 4 or 5.

    In fact it is 4. If you apply four random permutations to the vertices of the Petersen graph you will quickly come up with a way of covering all edges.

    But is there a nice way to see this? In particular, is it possible to arrange four Petersen graphs so that they cover each edge once or twice (so that deleting a complete graph leaves a trivalent simple graph remaining)? If so, what is this graph? If not, why not?

    Posted in open problems | Tagged , , | 4 Comments

    A surprise

    One of my birthday presents this year was a beautiful book by Christopher de Hamel, Meetings with Remarkable Manuscripts. The author, who is librarian at Corpus Christi College, Cambridge (a library to which he was once refused admission), and in his care are some impressive ancient manuscripts, including a gospel book brought to England by Augustine in the year 597; it is so old that it was produced before Jerome’s Latin Vulgate translation had become standard, and includes some passages from earlier translations.

    The book is structured as a sequence of interviews with celebrated manuscripts, as if they were human stars; we meet them in the libraries where they now reside, and are given an impression of their outward appearance before investigating the contents, history, and unexpected connections. The manuscripts include the Book of Kells and an early manuscript of the Carmina Burana.

    Reading it, I got quite a surprise. But let me fill in some background first.

    The pre-Socratic Greek philosophers where highly inventive and speculative. As well as arguing about whether “everything is change” or “change is impossible”, or whether the world is made out of water or fire or something else, they developed a number of models of the universe. Among these were a geocentric model rather like the one that prevailed until the time of Copernicus, and a heliocentric model (similar to that proposed by Copernicus) put forward by Aristarchus; and also two intermediate models.

    One of these, the “Egyptian” system of Herakleides, took into account the fact that Mercury and Venus behave very differently from the other planets, both in their sticking relatively close to the Sun rather than wandering around the whole Zodiacal belt, and in their waxing and waning in brightness as they moved. In hindsight it seems clear that, however the outer planets behave, there is clear evidence that the inner planets go round the Sun. The model proposed by Herakleides involved Mercury and Venus circling the Sun as it (like the other planets) moved round the earth.

    A more drastic revision had all the other planets (except the moon) circling the Sun as it moved round the earth: this model was later and perhaps independently proposed by Tycho de Brahe as a way of getting some of the advantages of the Copernican system while not falling foul of those who insist that the earth is fixed.

    Then along came Plato, who said that the most perfect form of motion is uniform motion in a circle; and Aristotle, who said that change and decay exist only in the sublunary sphere, and so all the planets must undergo uniform circular motion. This view held sway for more than a millennium and a half.

    Or at least, so goes received wisdom. But one of de Hamel’s manuscripts is the Aratea, in the university library in Leiden. It deals with astronomy, with vivid pictures of the constellations, but also includes a “planetarium”, which clearly shows Herakleides’ model with Mercury and Venus circling the Sun.

    This manuscript was produced at the court of Charlemagne, in his lifetime or a little after. It is a copy of a manuscript explaining the theories of Aratus of Soli, an astronomer who lived about 300BC, rendered into Latin. The original has not been found; according to de Hamel, a new copy was more important at the time than a possibly battered and damaged original, which could be thrown away once the copy had been made! But this shows clearly that some pre-Socratic Greek knowledge had not been lost by around the year 800. In fact, the planetarium is not part of Aratus’ work, and is probably taken from a calendar from the year 354.

    Even more intriguingly, de Hamel cites the work of modern astronomers who have examined this planetarium closely. If we assume that the scribes recorded the actual configuration of planets and stars at the time, and worked to 15 degrees accuracy, the configuration shown occurred on 18 March and 14 April 816, and not again (or before) for 98000 years.

    If this is correct, it gives us an astonishingly accurate dating of a mediaeval manuscript. According to a calculation by Bede a little earlier, 18 March was the date on which God created the universe (in the year 3952BCE), so this would be an important anniversary. Charlemagne had died two years earlier, and his son Louis the Pious would be crowned later in the year 816, so the date is plausible historically. There were dramatic developments in education and study in the reign of Charlemagne, driven by Alcuin of York who was his adviser in this early renaissance of classical learning.

    Arthur Koestler, from whose book The Sleepwalkers I have taken the account of Greek cosmology, admits that by the year 1000 some of the alternative Greek cosmological manuscripts were being rediscovered; but it seems that this happened earlier, or perhaps in some sense they had never been forgotten. Clearly there are currents here that I am not aware of!

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