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).


About Peter Cameron

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

2 Responses to Open University Winter Combinatorics Meeting

  1. Colin says:

    As a seasoned, hardened and numbed 35 year user of what is currently known as london midland, you camfe off lightly. And no doubt sensible information and apologies were scantly. They are too often given reluctantly

    • Ah, you are completely correct except for the fact that it was Virgin Trains. (I am an old man now, I can travel just as cheaply on Virgin as on London Midland.)
      The one bit of explanation we got was “They’ve put us on the slow line. I’ve no idea why.”

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s