On January 10, 2023, Mamadou Moustapha Kanté from the Université Clermont Auvergne gave a talk at the Discrete Math Seminar on the recognizability and the MSO definability for classes of matroids of bounded path-width having the strongly pigeonhole property. The title of his talk was “MSOL-Definable decompositions“.
Mamadou Moustapha Kanté, MSOL-Definable decompositions
I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step, I will discuss relations with decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain how to define in MSOL branch-decompositions for finitely representable matroids of bounded path-width. This is joint work with Rutger Campbell, Bruno Guillon, Eun Jung Kim, and Sang-il Oum.