Skip to content

Binary matroids with no K_5 minor

August 4, 2010

I gave my talk at the Maastricht workshop yesterday and so here are the slides (Maastricht talk).

Matroid theory is not especially well known (in fact, when he gave a talk here, Brian Alspach used a result from matroid theory and described the subject as “the one that is allocated the smallest and furthest away room in any conference that has parallel sessions”) and so usually it’s necessary to put a lot of basic definitions into any talk. Fortunately this occasion, where everyone is working in matroids, is an exception and so I could launch straight in.

In some sense, binary matroids are a generalization of graphs, and so any question that can be asked about graphs can be asked unchanged about binary matroids. In the 1930s Klaus Wagner proved the famous excluded minor result

A graph is planar if and only if it does not have the complete graph K_5 or the complete bipartite graph K_{3,3} as a minor.

He also gave a description of the graphs that do not have K_5  as a minor, and similarly the class obtained by excluding K_{3,3}.

We (that is,  me and my friends from Wellington NZ, Geoff Whittle and Dillon Mayhew) are trying to extend these two results to binary matroids and get descriptions of the exact structure of those classes. It turned out that the case for excluding K_{3,3} was tractable, though we ended up with a long 113 page paper that has just appeared in the Memoirs of the American Mathematical Society. But excluding K_5 seems much more difficult and we really don’t know where to go from here.

My talk basically describes what we’ve done and where we’re stuck!

Advertisements
No comments yet

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

%d bloggers like this: