From graph duals to matrix pivots: a tour through delta-matorids
12th November 2019, 11:00 am – 12:00 pm
Fry Building, 2.04
This talk will consider a variety of everyday graph theoretical notions --- duals, circle graphs, pivot-minors, Eulerian graphs, and bipartite graphs --- and will survey how they appear in the theory of delta-matroids. The emphasis will be on exposing the interplay between the graph theoretical and matroid theoretical concepts, and no prior knowledge of matroids will be assumed.
Matroids are often introduced either as objects that capture linear independence, or as generalisations of graphs. If one likes to think of a matroid as a structure that captures linear independence in vector spaces, then a delta-matroid is a structure that arises by retaining the (Steinitz) exchange properties of vector space bases, but dropping the requirement that basis elements are all of the same size. On the other hand, if one prefers to think of matroids as generalising graphs, then delta-matroids generalise graphs embedded in surfaces. There are a host of other ways in which delta-matroids arise in combinatorics. Indeed, they were introduced independently by three different groups of authors in the 1980s, with each definition having a different motivation (and all different from the two above). In this talk I'll survey some of the ways in which delta-matroids appear in graph theory. The focus will be on how the fundamental operations on delta-matroids appear, in different guises, as familiar and well-studied concepts in graph theory. In particular, I'll illustrate how apparently disparate pieces of graph theory come together in the world of delta-matroids.