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
| CREATOR | Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-02999