1. Model-theoretic methods for algorithmically tame graph classes
- Author
-
Benediktsson, Bjarki Geir, Adler, Isolde, and Macpherson, Dugald
- Abstract
The Johnson graphs J(n, k) and Hamming graphs H(d, q) are well-known families of finite graphs with strong symmetry properties, such as distance-transitivity. In this thesis we explore the model theory of these graphs and their infinite limits. A major focus is on Vapnik-Chervonenkis dimension and density, these are invariants of set systems historically of importance in statistical learning theory and extremal combinatorics, and highly relevant to first order structures which do not have the independence property. We show that the edge relation has VC-dimension 4 and VC-density 2 in the class of Johnson graphs and VC-dimension 3 and VC-density 2 on the class of all Hamming graphs. We also consider the limit theory Tj of the Johnson graphs as min(n, k, n-k) → ∞. We show that Tj is complete, describe the infinite models and prove that it is ω-stable of Morley rank ω, but not monadically dependent. When k is fixed, the limit theory of J(n,k) is totally categorical of Morley rank k. We also explore how certain graph operations affect the VC-dimension of the edge relation.
- Published
- 2021