Characterization of NIP theories by ordered graph-indiscernibles (Q450958)

It is known that a theory \(T\) is stable if and only if every infinite indiscernible sequence in a model of \(T\) is an indiscernible set. This paper proves a similar result in the larger setting of NIP theories, using the following generalization of indiscernible sequence, introduced by Shelah. Let \(M\) be an \(L\)-structure, \((b_i: i \in I)\) be a sequence of parameters from \(M\) indexed by an \(L'\)-structure \(I\). Then \((b_i:i \in I)\) is \(L'\)-generalized indiscernible in \(M\) if and only if, for all finite \(\overline{i}\), \(\overline{j}\) in \(I\) of the same length, if \(\overline{i}\) and \(\overline{j}\) admit the same quantifier-free type in \(I\) with respect to \(L\) then \((b_i: i \in \overline{i})\) and \((b_j : j \in \overline{j})\) have the same type in \(M\) with respect to \(L\). Now take \(L' = L_g = \{ <, R\}\) = the language of ordered graphs. Thus both \(<\) and \(R\) are binary relation symbols, the former for order and the latter for the edge relation. Let \(T_g\) be the \(L_g\)-theory of linearly ordered graphs (symmetric and without loops), \(K_g\) be the class of all finite models of \(T_g\). The main theorem of the paper says that a theory \(T\) is NIP if and only if every \(L_g\)-generalized indiscernible in a model of \(T\) indexed by an \(L_g\)-structure \(I\) with age equal to \(K_g\) is an indiscernible sequence (where the age of \(I\) is the class of all \(L_g\)-structures isomorphic to some finitely generated substructure of \(I\)). A key role in the proof is played by the \textsl{modeling property}, which is introduced in the following way, for an arbitrary \(L'\). Let \(U\) be the age of some \(L'\)-structure, then \(L'\)-generalized indiscernibles are said to have the modeling property for \(U\) if and only if \(I\)-indexed indiscernibles (for \(I\) any \(L'\)-structure with age \(U\)) can be found based on any \(I\)-indexed set. The modeling property can also be characterized in terms of Ramsey classes as follows, when \(L'\) is a finite relational language containing a binary relation symbol \(<\) for order: If \(U\) is the age of some linearly ordered \(L'\)-structure, then \(L'\)-generalized indiscernibles have the modeling property for \(U\) if and only if \(U\) is a Ramsey class.