Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes

arXiv2206.13765MaRDI QIDQ6403341FDOQ6403341

Authors: Jan Dreier, Sebastian Siebertz, Szymon Toruńczyk 

Publication date: 28 June 2022

Abstract: An indiscernible sequence $$ in a structure is an ordered sequence of tuples of elements which is very homogeneous in the sense that any two finite subsequences of the same length satisfy the same first-order formulas. We provide new characterizations of monadically stable and monadically NIP classes of structures in terms of indiscernible sequences by showing that they impose a strong structure on their neighborhoods. In particular, we show that every formula~$$, where $x$ is a single free variable, has alternation rank at most $2$ over every sufficiently long indiscernible sequence in a monadically NIP class. We provide a second new characterization of monadically stable classes of graphs in terms of a new notion called flip-wideness. Flip-wideness generalizes the notion of uniform quasi-wideness, which characterizes nowhere dense classes and had a key impact on the combinatorial and algorithmic treatment of nowhere dense classes. All our proofs are constructive and yield efficient algorithms.

This page was built for publication: Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403341)