Old Codger’s Combinatorics Conference

Wednesday was the Old Codger’s Combinatorics Conference at the University of Reading, a one-day meeting organised by Anthony Hilton. The position of the apostrophe is correct: it refers to the fact that Anthony admits that he is an old codger but that the meeting is open to anyone, even those not fitting this description. (Almost all on-line dictionaries insist that an old codger must be male.) He also claims that he continues to run this meeting to maintain some activity in combinatorics at the University of Reading, a mathematics department associated with Richard Rado, Crispin Nash-Williams, David Daykin, and Anthony himself.

Sometimes the weather at this time of year can be beautiful, and the Reading campus looking lovely with autumn leaves under blue skies and a variety of waterfowl on the lake. But this time it was wet; Rosemary and I started out round the lake when the rain seemed to have stopped, but were thoroughly drenched by the time we got back.

The highlight of the meeting was a talk by Imre Leader on new work he and Paul Russell have done on partition regularity for inhomogeneous equations, going right back to Rado’s work at the beginning of the subject. A system Ax = b over the integers is partition regular if, in any finite colouring of the natural numbers, you can find a monochromatic solution to the equations. We are interested here in the inhomogeneous case, where the vector b is non-zero. In this case, if the system has a constant solution (with the values of all variables equal), it is clearly partition regular. If s denotes the column vector which is the sum of all the columns of A, then this holds if and only if b is a multiple of s (say b = as, in which case putting all variables equal to a gives a solution).

Rado proved the converse, that is, if the system is partition-regular then there is a constant solution. Imre began by taking us through the proof. First he did the case where there is just one equation. Then rather complicated arguments do the general case. Various authors since have extended this, using algebraic techniques of increased sophistication, to extend from the integers to other rings (so the result holds for integral domains, and for Noetherian reduced rings).

Remarkably, what Imre and Paul have done is to handle all commutative rings with identity, not by elaborating the existing arguments, but by going back to Rado’s original proof for one equation and extending it to any number. The trick is that, although we work over a ring R, we are going to think of it in the proof as an abelian group and essentially ignore the multiplication after the very first step. So here is the proof.

We suppose that there is no constant solution. Let K be the subgroup of Rn consisting of all multiples of s. By assumption, b is not in K. Now let H be a subgroup of Rn which is maximal with respect to containing K but not b. Then Rn/H is an abelian group containing a non-zero element (the image of b) which lies in every non-zero subgroup (if not, we could replace H by a larger subgroup). Now such abelian groups are not too hard to characterise: they consist of finite cyclic p-groups and Prüfer p-groups, for some prime p. The latter consists of all the p-power roots of unity in the complex numbers; so, in either case, the group can be represented on the unit circle. Now dividing the circle into sufficiently small intervals allows the construction of a colouring with no monochromatic solution of the original system.

After this lecture, Anthony Hilton fetched in from the common room the bust of Richard Rado from the common room next door, where it sits unnoticed in a corner (despite Anthony’s attempts to have it more prominently displayed).

After that, a briefer account of the rest.

I was the first speaker. I talked about equitable partitions of Latin square graphs, a topic I have described here. Partly inspired by some work I am currently doing with Sanming Zhou from Melbourne, I introduced the topic with a few words about perfect 1-codes in graphs. I sometimes think that, had we mentioned this in the introduction of the paper, it might not have been rejected without refereeing by a journal with the words “designs” and “codes” in the title.

Dudley Stark talked about a theorem he and Nick Wormald have spent the past twenty years proving: estimates for the probability that a random graph G contains a fixed graph H. They handle both the Gn,m and Gn,p models (the answers are slightly different), and they are able to extend the range of parameters previously handled (even in the case where H is a triangle). The idea is quite simple, but the details extremely complicated. Dudley said they never doubted that the result was true but were not sure whether they would be able to produce a proof.

Richard Mycroft talked about the function t(T), where T is an edge-oriented tree on n vertices, defined to be the smallest N such that T is embeddable in every N-vertex tournament. It was conjectured by Sumner that 2n−2 vertices suffice; this is known for large n (“regularity lemma large”) and small n (up to 8, maybe), and thought to be true for intermediate values. A tree T is called unavoidable if t(T) = n; Richard and his colleague have shown that almost all trees are unavoidable.

Peter Larcombe talked about some rather different mathematics, involving Catalan numbers and Catalan polynomials. This touched on Newton–Raphson and other approximation methods including Padé approximants, and he also mentioned some new results about powers of 2×2 matrices (and more generally, tridiagonal matrices) which he has observed and proved, challenging us to say if we had seen such things before (no one had). It all went by rather fast; I hope to say more on some later occasion.

The final talk was by Matthew Johnson, who talked about almost bipartite graphs, those whose vertex set can be partitioned into an independent set and a set inducing a forest. It is known that a graph of maximum degree 3 is almost bipartite; Matthew and his colleagues have found a different proof of this which gives a linear-time algorithm for finding the partition. The application is to a recolouring problem. Given two proper colourings of a graph, with the same set of colours, is it possible to move from one to the other by changing the colour of one vertex at a time (retaining the properness)? In some cases they have a simple algorithmic answer to this question.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, history and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.