NIP theory

Remarks

Example: the theory of dense linear orders without endpoints is NIP. By quantifier elimination, a formula $\varphi(x; \bar y)$ defines, for each parameter $\bar b$, a union of at most $k$ points and intervals. The endpoints are entries of $\bar b$, and $k$ depends only on $\varphi$. Such a family cannot cut out all $2^n$ subsets of a set of $n$ points once $n$ is large. It is a standard fact that it suffices to check formulas with $\bar x$ a single variable.

Non-example: the theory of the Rado graph is not NIP. For the formula $x E y$, take distinct vertices $a_1, \ldots, a_n$; by the extension property, for each $J$ there is a vertex $b_J$ adjacent to $a_i$ exactly when $i \in J$.

Equivalently, $T$ is NIP if for every formula $\varphi(\bar x; \bar y)$ and every model $M$ of $T$, the family $\set{\varphi(M; \bar b) : \bar b \in M}$ has finite VC dimension. Every stable theory and every o-minimal theory is NIP.