Model Theory of Johnson Graphs

A Johnson graph $J(n,k)$ is a graph whose vertices are the k-element subsets of an underlying set of size n where two vertices are adjacent if they intersect in a subset of size $k-1$. We extend the definition to allow infinite parameters and we study a natural limit theory TJ of Johnson graphs. We show that TJ is complete and we give an axiomatisation of TJ, from which we obtain a complete description of the models of TJ. We use this to show tameness properties of TJ, namely that TJ is $ω$-stable of Morley rank $ω$, but not monadically dependent. In particular it follows that the class of all finite Johnson graphs is stable, and therefore dependent but not monadically dependent.