Model Theory of Johnson Graphs
In the authors' words
A Johnson graph is a graph whose vertices are the -element subsets of an underlying set of size where two vertices are adjacent if they intersect in a subset of size . We extend the definition to allow infinite parameters and we study a natural limit theory of Johnson graphs. We show that is complete and we give an axiomatisation of , from which we obtain a complete description of the models of . We use this to show tameness properties of , namely that 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.
Main resultThe abstract does not state a limitation.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.