Online talk: Dillon Mayhew

Mon, April 27 3pm ET (8pm BST, 7am Tue NZST)
Dillon Mayhew, Victoria University of Wellington
Definability and non-definability for classes of matroids
Youtube Link

Monadic second-order logic provides a bridge between the theory of computation and the structure of graphs and matroids. So it is natural to ask which classes can be characterised by a sentence in monadic second-order logic. In some sense this problem is uninteresting for graphs, since every minor-closed class can be defined in this way. But there are minor-closed classes of matroids that can not be defined in monadic second-order logic. This talk is going to discuss the boundary between definability and non-definability, with special reference to classes of gain-graphic matroids.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.