一句话：在任意关系结构上引入翻转与翻转独立，证明其与模型上的分叉独立等价，统一单子稳定类的组合刻画。
本文研究模型论中的单子稳定与更一般的单子依赖（NIP）这类驯顺性条件，以及它们在一阶逻辑模型检测中的算法意义：对固定单子稳定图类，模型检测已知为固定参数可处理，单子依赖类则被猜想可处理。既有组合刻画均基于图翻转操作。作者将翻转和翻转独立推广到任意关系结构，把单子稳定图类的组合刻画提升到单子稳定关系结构类；证明在单子稳定结构中，翻转独立与（模型上的）分叉独立等价，从而用组合方式刻画这一稳定理论中的核心逻辑概念，并为单子稳定图及 Gaifman 图无处稠密的关系结构中的分叉独立给出更精确的描述。
Monadic stability and the more general monadic dependence (or NIP) are tameness conditions for classes of logical structures, studied in the 80’s in Shelah’s classification program in model theory. They recently emerged in algorithmic and structural graph theory and finite model theory as central notions in relation with the model checking problem for first-order logic: the problem was shown to be fixed-parameter tractable for inputs which come from a fixed class of graphs which is monadically stable, and is conjectured to be tractable in all monadically dependent classes. Several combinatorial characterizations of such graph classes turned out to be essential in their algorithmic treatment; they are all based on the fundamental operation of "flipping" a graph.We introduce the notions of flips and flip independence in arbitrary relational structures. We lift prior combinatorial characterizations of monadically stable graph classes to monadically stable classes of relational structures. We show the equivalence of flip independence with forking independence (over models) – a logical notion of paramount importance in stability theory – in monadically stable structures, shedding new light on the relevance of flips, also characterizing forking independence (over models) combinatorially. We give more precise descriptions of forking independence in the case of monadically stable graphs, and relational structures with a nowhere dense Gaifman graph.
DOI 原文 ·
@inproceedings{paperbot8670,
title = {Flipping and Forking},
author = {Wojciech Przybyszewski and Szymon Toruńczyk},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00070}
}