Model Theory of Johnson Graphs

@misc{benediktsson2026model,
  title = {{Model Theory of Johnson Graphs}},
  author = {Bjarki Geir Benediktsson and Dugald Macpherson and Isolde Adler},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.40054},
  eprint = {2610.40054},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40054},
}

TY  - UNPB
TI  - Model Theory of Johnson Graphs
AU  - Bjarki Geir Benediktsson
AU  - Dugald Macpherson
AU  - Isolde Adler
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.40054
UR  - https://arxiv.org/abs/2610.40054
AB  - A \emph{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 T_𝒥 of Johnson graphs. We show that T_𝒥 is complete and we give an axiomatisation of T_𝒥, from which we obtain a complete description of the models of T_𝒥. We use this to show tameness properties of T_𝒥, namely that T_𝒥 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.
ER  -