Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. Almost-wideness is a notion that was central in different characterisations of nowhere dense classes of graphs, and in particular the game-theoretic one. In this talk I will present the flip-flatness notions and conjectures about the characterization of strongly flip-flat graph classes. Then, I will present a proof that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide, making a step towards their characterisation. A consequence is a characterization of strongly flip-flat graph classes with low rank-depth colourings.
This is a joint work with F. Ghasemi, J. Grange and F. Madelaine.
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“.
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.
