Biased graphs, matroids, and excluded-minor characterisations

18^th February 2025, 13:00 ELEC204, 2th Floor Lecture Theatre EEE
Dillon Mayhew
University of Leeds

Abstract

Very frequently in discrete mathematics, we are interested in a class of objects organised under a substructure relation. For example, we may be interested in the class of graphs under subgraphs, under induced subgraphs, or under minors. A set of objects that is closed downwards under one of these relations can be characterised by looking at the minimal objects not in the class. In the case that we are concerned with the minor relation, these minimal objects are known as excluded minors. The Kuratowksi-Wagner Theorem famously characterised planar graphs by showing that there are exactly two excluded minors: K3,3 and K5. Robertson and Seymour showed that any class of graphs that is downwards-closed under the minor relation can be characterised by a finite set of excluded minors.

In this talk we will focus on the minor relation applied to two different (but related) classes of objects: matroids and biased graphs. Matroids can be seen as abstractions and generalisations of graphs. Some matroids can be represented by sets of vectors. These are known as representable matroids. Others can be represented by biased graphs, which are graphs along with distinguished classes of cycles. A famous conjecture by Rota states that certain classes of representable matroids can be characterised by finitely many excluded minors. In this talk we will give a gentle introduction to matroids and talk about progress towards Rota's conjecture and its variants.

Biography

Dillon Mayhew is a professor in the School of Computer Science at the University of Leeds, having arrived there in 2023. Before that, he was at the School of Mathematics in Te Herenga Waka, Victoria University of Wellington in New Zealand. His research interests are based in discrete structures such as matroids and graphs as well as the expressive power of logical languages and their connections to the theory of computation.