

























Abstract:We study monadic dependence of binary relational structures including at least one antisymmetric relation.
Our cornerstone result gives sufficient conditions for proving that a structure is monadically dependent by only considering some of its reducts, assuming they are structurally well-behaved and compatible enough. As an application, we consider some reorientation rules preserving monadic dependence of binary structures, as well as replacement of one antisymmetric relation with bounded independence number by another. Then, we apply our main (technical) result to the study of twin-width in two ways.
First, generalizing the fact that twin-width boundedness is equivalent to being expandable by a linear order into a monadically dependent class, we prove that it is also equivalent to being expandable by an oriented graph with bounded independence number (for instance by a poset with bounded width or by a tournament), and that FO-model checking is fixed-parameter tractable on such an expansion.
Second, we show delineation by twin-width for some new classes of oriented graphs, including oriented split graphs and local tournaments. In all these cases, we also obtain fixed-parameter tractability of FO-model checking.
From: Patrice Ossona de Mendez [view email]
[v1]
Wed, 17 Jun 2026 11:16:11 UTC (200 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。