Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes
share
An indiscernible sequence (a̅_i)_1≤ i≤ n 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 ϕ(x,y̅), 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.
READ FULL TEXT