  We prove that for any monotone class of finite relational structures, the
first-order theory of the class is NIP in the sense of stability theory if, and
only if, the collection of Gaifman graphs of structures in this class is
nowhere dense. This generalises to relational structures a result previously
known for graphs and answers an open question posed by Adler and Adler (2014).
The result is established by the application of Ramsey-theoretic techniques and
shows that the property of being NIP is highly robust for monotone classes. We
also show that the model-checking problem for first-order logic is intractable
on any class of monotone structures that is not (monadically) NIP. This is a
contribution towards the conjecture of Bonnet et al. that the hereditary
classes of structures admitting fixed-parameter tractable model-checking are
precisely those that are monadically NIP.
