SEMINAR: Groups and Combinatorics Seminar, Graphs are to matroids what ribbon graphs are to ...?

Steven Noble (Brunel University)

will speak on

Graphs are to matroids what ribbon graphs are to ...?

at 3pm Friday April the 11th in Weatherburn Lecture Theatre.

Abstract:

Much of the combinatorial structure of an abstract connected graph is encoded in its set of spanning trees. These form one of the canonical examples of the bases of a matroid. Ribbon graphs contain extra topological information on the embedding of the underlying abstract graph in a surface. The structures playing the role of spanning trees are the subgraphs having one boundary component. The combinatorial structure which they form is a delta-matroid, which roughly speaking is like a matroid except that the bases do not need to have the same size. We will discuss three classes of delta-matroids, some natural operations on ribbon graphs which correspond to natural operations on delta-matroids, give an excluded minor theorem for one of the classes of delta-matroids and, time-permitting describe the Bollobas-Riordan polynomial which forms one way of generalizing the Tutte polynomial to ribbon graphs.