Conference for Geoff Whittle

In 2013, when I retired from Queen Mary (my first, unsuccessful, attempt at retiring), Geoff Whittle came and spoke at the conference my colleagues organised for me. He is also someone who has appeared on these pages a few times.

Me and Geoff Whittle

So I have been very happy to return the favour. Even though Geoff’s field is matroid theory, where I haven’t made many contributions, there are very few mathematicians (indeed, very few people) in the world who are as much on my wavelength as Geoff; in the pub the evening before the conference we discovered that for both of us, our favourite poem is T. S. Eliot’s Four Quartets, that we resist reading what literary critics have to say about it, and that we have used snippets from it in describing mathematical processes.

I will say a bit about some of the talks at the conference, which I found very stimulating. I would like to discuss everything, but life is too short … Indeed, since I am not a matroid theorist, my selection will be a bit biased; perhaps a more balanced account will appear on the Matroid Union blog. (Matroid theorists admit that they are a small and closely-linked community; they all know the difference between James and Jim, for example.)

Day 1

James Oxley opened the meeting with a talk about Geoff’s early career. I met him fairly late on, and didn’t realise how many things he had done before settling down to work on Rota’s conjecture with Jim Geelen and Bert Gerards. Between school and university, he worked in various mines in Australia, and saved up money which he spent on travelling around South-East Asia; between undergraduate and PhD, he taught in a girls’ high school in Tasmania. The main function on the talk was the critical exponent of a matroid, and some of Geoff’s results and conjectures in this general area.

James described Tutte’s definition of a “tangential k-block”. Someone asked why he had called it that; James’ reply was that he couldn’t get inside Tutte’s head to see the geometric intuition behind the name.

Rob Goldblatt, who may have been the department chair when Geoff was appointed in Wellington, began with some reminiscences about the history of the department. In 1919, Duncan Sommerville (of Dehn–Sommerville equations fame) was the entire mathematics department in what was then Victoria College. (Later in the St Andrews History of Mathematics I found some more interesting things. Sommerville had been a student, and then a lecturer, at St Andrews before going to New Zealand; and he had tutored Alexander Aitken by correspondence after the professor of mathematics at Otago had a nervous breakdown. Among the links opened up here are the facts that Geoff Whittle was the inaugural Aitken lecturer, and one of the places on the itinerary of his lecture tour of Britain was St Andrews.) Rob made the very good point that matroid theory, especially in Geoff’s hands, maintains the Wellington tradition of excellence in geometry.

His talk was about mereotopology, a formulation of topology where the basic objects are regions rather than points. According to Wikipedia, this was invented by A. N. Whitehead, although Rob gave credit to the work of Lesnievski. The relation to the foundations of mathematics is that it is a first-order theory with a single binary relation on the set of regions, whereas topology is not first-order on points. The idea has been taken up by various computer scientists. To be specific, the elements are the “regular” closed sets, those which are the closure of their interior: these form a Boolean algebra, where join is as usual, meet is the closure of the interior of the intersection, and complement is the closure of the interior of the set-theoretic complement. The added binary relation describes “connection” (perhaps better described as “closeness”) of regions. The Stone duality between Boolean algebras and Stone spaces (compact Hausdorff 0-dimensional spaces) extends to a duality between BCAs and T0 mereocompact mereotopological spaces. I will spare you the definitions.

Here is a small plum from Petr Hlineny’s talk. Suppose that you have an oracle which tells you whether a given graph is 3-colourable. Can you use it to find an explicit 3-colouring in polynomial time? The answer is yes, and the trick is very simple: I will give it later.

Stefan van Zwam showed a nice theorem about the correspondence between binary matroids and binary codes. If a minor-closed class C of matroids contains (matroids corresponding to) an asymptotically good sequence of codes (that is, with both rate and minimum distance over length are bounded away from zero, then it must be the class of all binary matroids. (A similar result holds for representable matroids over any finite field, but we have to exclude the case that the class contains all matroids representable over the prime field.) The proof used two theorems of Kashyap proving the result for graphic and cographic matroids, and a theorem of GGW asserting that any minor-closed class of binary matroids has the property that its sufficiently connected members form a perturbation of the class of sufficiently connected graphic or cographic matroids.

Stefan showed a picture of Geoff among the examiners at his (Stefan’s) PhD defence in Eindhoven. I was interested to see, on the wall behind them, a picture of my good friend Jack van Lint, from whose book I learned Shannon’s theorem about the existence of asymptotically good codes.

Finally Gordon Royle talked about his attempts to find the excluded minors for the class of graphs with contraction degeneracy at most 4, a problem which seems to be just out of reach at present but has connections with real chromatic and flow roots of graphs. He began by showing a conference photograph containing many people who were either here or well known to some of us, and identified it as the ACCMCC in Taupo in 2004.

Day 2

Charles Semple, Geoff’s first student, began the day’s proceedings with a talk mostly concerned with the question: for which sets of fields can a matroid be representable over just those fields, and can we describe the matroids? A sample theorem: a matroid is representable over GF(3) if and only if it is representable over GF(3) and GF(q) for some q in the set {2,4,5,7,8}.

By the end of his talk, we had met another theorem asserting that every flower is either an anemone or a daisy. (I am not quite sure, but you might have to exclude some “ground-dwelling junk”.)

Will Critchlow bravely tackled the question of what a random matroid looks like. It is thought that most rank r matroids on n points are sparse paving matroids: these are matroids in which every circuit has cardinality r, and any two circuits meet in at most r−2 points. Thus, the collection of circuits (which specifies the matroid) is an independent set in the Johnson graph J(n,r), a graph well known to association scheme theorists: the vertices are the r-subsets of an n-set, two vertices joined if they intersect in r−1 points.

The Johnson graph has large independent sets. Graham and Sloane, following a suggestion of Knuth, observed that, if the vertex set is {1,…,n}, then the collection of r-sets with sum congruent to k (mod n) is an independent set, so there is some independent set whose size is at least a fraction 1/n of the number of vertices in the graph. A sparse paving matroid is of GS type if its circuits form a subset of an independent set of this form, for some ordering of {1,…,n}. There are many such matroids but whether they predominate in an enumeration is not clear.

Mike Newman told us about the non-existence of axioms for representable matroids. This is a question which some people think that Peter Vamos solved, but in fact he didn’t; the axioms for a matroid are monadic second order, and so it is only reasonable to ask if there is a monadic second order axiom for representability. Mike, with Dillon Mayhew and Geoff Whittle, have shown by an ingenious argument that there is not. This involves looking carefully about what a monadic second order axiom can actually say about a matroid, and showing that for any such axiom there are representable and non-representable matroids which it does not distinguish.

Carolyn Chun talked about delta-matroids. Briefly: a ribbon graph is a structure equivalent to a graph embedded in a surface. (Fatten up each vertex of the graph to a small disc, and each edge to a small strip. These are more general than graphs since edges may be twisted.) Now a quasi-tree in a ribbon graph is a subgraph with only one boundary component. Just as the spanning trees in a graph are the bases of a matroid, so the quasi-trees in a ribbon graph are the “feasible sets” in a structure called a delta-matroid. There are many connections with matroid theory, and Carolyn made the subject look very attractive; but I won’t attempt to say more.

Day 3

After three beautiful days, the rain came this morning; no sunlight sparkling on the harbour or blue mountains on the other side.

The first talk was by Jim Geelen, one of the three knights who had succeeded in their quest for the Holy Grail, the proof of Rota’s conjecture. The conjecture asserts that, for any fixed finite field F, the (minor-closed) class of matroids representable over F is defined by a finite number of excluded minors. The quest took not too far short of twenty years, and is a massive piece of work. Jim described very well the highs and lows of the enterprise which he, Bert Gerards and Geoff Whittle underwent. One small example: the three-way collaboration arose when Jim was at the Fields Institute and had double-booked, inviting the other two to come and work with him in the same week; the only way he could achieve that was to get all three to work together, showing that the set of F-representable matroids of bounded branch-width is well-quasi-ordered. (A false lead, as it turned out, but it stoked their enthusiasm for a structure theorem for representable matroids, extending the Robertson–Seymour theory for graphs, which they achieved in 2010.

Next, Henry Crapo talked about another Rota conjecture, his basis conjecture. This asserts that, in a matroid of rank r, if we take any r bases (not necessarily distinct), then we can order them so that, when we take them as the rows of a matrix, the columns also form bases. (This is unknown even in the linear algebra context.) He first observed that the converse is true: if a set of r-element sets has this property then it is the set of bases of a matroid. (We only need the property for r-tuples of the form (A,A,…,A,B). For suppose the property holds for such a tuple. The first r−1 rows of the matrix form a partial Latin square, which can be completed uniquely to a Latin square; the correspondence from the last row of this square to the last row of the given square is a map from A to B which shows the exchange axiom for A and B. Henry thinks the conjecture is true, but had been using the computer to look for counterexamples, so far without finding any.

A cyclic flat in a matroid is a flat which is a union of cycles. Unlike most matroid concepts (bases, circuits, flats, rank function), the cyclic flats do not determine the matroid uniquely. However, they form a lattice of subsets of the ground set, and with the extra information about the rank of each of these sets, the matroid is determined. Bonin and de Meir have given axioms for a matroid in terms of its cyclic flats and their ranks. Kadin Prideaux told us about work in progress: given a lattice of subsets of a set, can we determine the possible ranks for which they form as the lattice of cyclic flats of a matroid? The axioms give a bunch of linear inequalities for the values, and so determining them is an integer programming problem. Sad to say, the admissible polytope can have non-integral vertices, so the job won’t be easy.

(Unfortunately, he went through the definition of a cyclic flat very quickly, while I was still making notes on his first slide, so I missed it, and had to look it up later.)

After lunch, there were just two talks. Rod Downey told us about using logic to investigate invariants (in a very general extent: Ulm invariants, homotopy groups, etc.) He ranged from Shelah’s dichotomy theorem (announced by an abstract entitled “Why I am so happy”), through Borel equivalence and reductions, to computational classification and the arithmetic and analytic hierarchy. A natural problem in the classification theory of torsion-free abelian groups lies, remarkably, on level 7 of the arithmetic hierarchy.

Rod also claimed that Geoff continued Wellington’s strong tradition in logic. I think both his statement and Rob Goldblatt’s are correct.

Dillon Mayhew closed the meeting with a talk on some early work of his with Geoff about the number of inequivalent representations of a 3-connected matroid with no U3,6 minor. One slightly remarkable thing was that in looking over his slides at lunchtime he had found an error in the proof, which he had managed to fix on the spot.

And so the conference closed, and we drifted off.

Postscript

Here is the solution to Petr Hlineny’s puzzle: given an oracle for 3-colourability, find a 3-colouring.

First, of course, check with the oracle that the graph is really 3-colourable. Then add an edge not already present in the graph, and ask the oracle if this graph is 3-colourable. If it says “yes”, leave the edge in and repeat the step. If it says “no”, remove the edge but note that its ends must have the same colour in any 3-colouring. As the process proceeds, we are approaching a complete 3-partite graph from below (with the edges present) and above (with the information on the partition).

The trick can be adapted to other situations: can you think of any?

Advertisements

About Peter Cameron

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

2 Responses to Conference for Geoff Whittle

  1. Peter says:

    This is a pretty standard trick in CS to show that a decision problem gives you a constructive answer – it’s the motivation for why we should care about the decision problem. If you think about it, you really don’t care if there is a procedure which just tells you whether a graph is Hamiltonian or not; if you think you want to know the answer, you will pretty much always mean you want to be shown a Hamilton cycle or told none exists, and the same goes for most other decision problems.

    Just for completeness, if you have any property which is monotone (increasing or decreasing) then this trick (removing and adding elements respectively) works. The annoying case is when your property is not monotone and you actually have to do work.

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 )

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