Title: Graphs are to matroids as embedded graphs are to what?
| Speaker: | Iian Moffatt |
| Affiliation: | Royal Holloway, University of London |
| Room: | MC 5501 |
Abstract: Matroid theory is often thought of as a generalisation of graph theory. Many results in graph theory turn out to be special cases of results in matroid theory. This is beneficial in two ways. Firstly, graph theory can serve as an excellent guide for studying matroids. Secondly, matroid theory can lead to new, and more general, results about graphs. Thus graph theory and matroid theory are mutually enriching.
In this talk I will be interested in embedded graphs (i.e., graphs in surfaces), rather than abstract graphs. By moving from an embedded graph to a matroid we generally loose all of its topological information. Thus matroids do not appear to provide a `correct' generalisation of embedded graphs. If matroids don't, what do? In this talk I will propose that delta-matroids play the role of matroids in topological graph theory. Delta-matroids were introduced by Bouchet, and are defined by relaxing one of the axioms of a matroid. I will show that results about embedded graphs can be understood as results about delta-matroids, and that embedded graphs provide an excellent guide for studying delta-matroids. Throughout this talk I will emphasize that there is a direct analogy with the classical matroid-graph connection. Also I will not assume any familiarity with matroids.
This is joint work with Carolyn Chun, Steven Noble and Ralf Rueckriemen.