Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width
Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim, Sang-il Oum
Abstract
Let be a finite field. We prove that there is an MSO-transduction which, given an -representable matroid of path-width k, produces a branch-decomposition of width at most f(k), for some function f. As a corollary, any recognizable property of -representable matroids with bounded path-width is definable in MSO logic, and therefore recognizability is equivalent to MSO-definability on classes of -representable matroids of bounded path-width. This generalizes the result of Bojańczyk, Grohe and Pilipczuk [Logical Methods in Computer Science 17(1), 2021] which asserts the equivalence of the two notions on graphs of bounded linear clique-width.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext ba706c5f-a448-40a5-88f4-90500d6c006aRelated papers
- Linear rankwidth meets stabilityJaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, Sebastian SiebertzSODA 2020
- Regular Grammars for Sets of Graphs of Tree-Width 2Marius Bozga, Radu Iosif, Florian ZulegerLICS 2025
- Low Rank MSOMikolaj Bojanczyk, Michal Pilipczuk, Wojciech Przybyszewski, Marek Sokolowski et al.LICS 2026
- Graphs of unbounded linear cliquewidth must transduce all treesMikolaj Bojanczyk, Pierre OhlmannLICS 2025
- Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank InequalitiesKristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász et al.SODA 2026
