Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width
Let ${\mathbb{F}}$ be a finite field. We prove that there is an MSO-transduction which, given an ${\mathbb{F}}$-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 ${\mathbb{F}}$-representable matroids with bounded path-width is definable in MSO logic, and therefore recognizability is equivalent to MSO-definability on classes of ${\mathbb{F}}$-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.
Authors
- Bruno Guillon (ORCID: https://orcid.org/0000-0003-1630-3404)
- Rutger Campbell
- Mamadou Moustapha Kanté (ORCID: https://orcid.org/0000-0003-1838-7744)
- Eun Jung Kim (ORCID: https://orcid.org/0000-0002-6824-0516)
- Sang-Ll Oum
Institutions
- Centre National de la Recherche Scientifique (FR)
- University of Clermont Auvergne (FR)
- Institute for Basic Science (KR)
- Korea Basic Science Institute (KR)
- Clermont Université (FR)
Publication Details
- Published
- 2025-06-23
- DOI
- https://doi.org/10.1109/lics65433.2025.00057
- Primary Topic
- graph theory and CDMA systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00