Transducing Linear Decompositions of Tournaments

Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté · 2026

Read Transducing Linear Decompositions of Tournaments by Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-02999.txt.

Description

Colin Geniet, Fatemeh Ghasemi, and Mamadou Moustapha Kanté work in logic and graph theory. Their topic is decompositions of tournaments. A tournament is a graph where every pair of vertices is joined by a single directed edge. A known result by Bojańczyk, Pilipczuk, and Grohe says that for graphs of bounded linear clique-width, good decompositions can be produced by a transduction in a rich logic called CMSO. The authors show tournaments need much less machinery.

For tournaments of bounded linear clique-width, a first-order transduction, written in the weakest standard logic, already suffices to produce the decompositions. That fact has a clean consequence: over this class of tournaments, the logics CMSO and existential MSO turn out to be equivalent. The result sharpens the boundary between what weak and strong logics can express.

Catalog record

CREATORColin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE87 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-02999

Browse the full library · About the Tower of Babel