  Monadically stable and monadically NIP classes of structures were initially
studied in the context of model theory and defined in logical terms. They have
recently attracted attention in the area of structural graph theory, as they
generalize notions such as nowhere denseness, bounded cliquewidth, and bounded
twinwidth.
  Our main result is the - to the best of our knowledge first - purely
combinatorial characterization of monadically stable classes of graphs, in
terms of a property dubbed flip-flatness. A class $\mathcal{C}$ of graphs is
flip-flat if for every fixed radius $r$, every sufficiently large set of
vertices of a graph $G \in \mathcal{C}$ contains a large subset of vertices
with mutual distance larger than $r$, where the distance is measured in some
graph $G'$ that can be obtained from $G$ by performing a bounded number of
flips that swap edges and non-edges within a subset of vertices. Flip-flatness
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. To obtain this result, we develop tools
that also apply to the more general monadically NIP classes, based on the
notion of indiscernible sequences from model theory. We show that in
monadically stable and monadically NIP classes indiscernible sequences impose a
strong combinatorial structure on their definable neighborhoods. All our proofs
are constructive and yield efficient algorithms.
