Matroids at La Vacquerie – 2013

Stefan and I (and others) have been idly talking about putting together a matroid blog for some time, and it was at a workshop of Henry Crapo’s that we finally put the plan into action, so I thought that I would devote my inaugural post to writing a little about the meeting.

Henry featured prominently in the early history of matroid theory, and his name will be familiar to those acquainted with matroid enumeration. He, along with coauthors John Blackburn and Denis Higgs, was the first to use a computer to count and catalogue matroids. Their article, published in 1973, describes a catalogue of all 1095 simple matroids with up to eight points. Incidentally, my proudest mathematical possession, given to me by Dominic Welsh, is a copy of the technical report by Henry and his coauthors. The cover is a thing of intricate beauty:

In case you can’t see, this is actually a piece of text. It says ‘The Henry Crapo Group presents the incredible catalogue of 8 point geometries: see single element extensions grow before your eyes’.

Henry now lives in the small French village of La Vacquerie-et-Saint-Martin-de-Castries, about an hour’s drive north of Montpellier. His house is a large villa, which he has fitted out with all the equipment needed for a small mathematics workshop. In the last week of June, about a dozen matroid theorists descended. As was the case in 2011, when he held his last meeting, Henry delved deep into his wine cellar, and brought in his friend Samuel to provide two home-cooked meals a day. When describing this arrangement to friends and family, it’s hard not to detect a note of envy (resentment, even?). What they don’t realise is that, although we may be averaging ten courses of food and one bottle of wine per person per day, we manage to get a fair bit of mathematics done.

In between picnics, of course.

Now that I reread Gordon Royle’s description of Henry’s 2011 meeting, I see he had the same experience that we did while driving in central Montpellier. Online maps seem to ignore one-way markings (which are ubiquitous), and also indicate the existence of many streets that, in the off-line world, are solely the reserve of trams. We had a merry time getting to our hotel. Stick to public transport is my recommendation.

One of the major themes of the 2013 meeting was the ongoing sage-matroids project, appropriately enough, given Henry’s position in the history of matroid computation. The project was initiated after a meeting in Wellington in 2010, and has been steaming along since. Rudi Pendavingh and Stefan van Zwam (with contributions from Gordon Royle and Michael Welsh) have done a massive amount of work on an addition to the open-source mathematics package sage. The package is now very useable; I regularly rely on it in my research. No doubt Stefan will have more to say about the package in a future post.

I will attach slides from some of the talks at the end of this post, but let me mention one seminar that quite nicely relates to Henry’s role in the development of matroid theory. Rudi Pendavingh, alongside Nikhil Bansal and Jorn van der Pol, has been working on improving bounds on the number of matroids with a given number of points. They have produced a significant decrease in the best upper bound, so that it now quite closely resembles the best known lower bound (although, unfortunately, we have to apply logarithms twice in order to really see the resemblance!). The lower bound is due to Knuth, and provides a lower bound on the number of matroids by explicitly finding families of sparse paving matroids. Thus Rudi and his coauthors have provided some more circumstantial evidence supporting the conjecture that sparse paving matroids dominate the collection of all matroids. This conjecture seems to date back to Dominic Welsh, and was inspired by… the catalogue produced by Blackburn, Crapo, and Higgs!