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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width

Bruno Guillon, Rutger Campbell, Mamadou Moustapha Kanté, Eun Jung Kim et al.
graph theory and CDMA systems
article

Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width

Bruno Guillon, Rutger Campbell, Mamadou Moustapha Kanté, Eun Jung Kim, Sang-Ll Oum
article en

Abstract

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.

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)
Openalex Percentile: Top 72%
graph theory and CDMA systems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width — Bruno Guillon, Rutger Campbell, et al. · (2025) | TGRS Research Map | TGRS