  VC-dimension and VC-density are measures of combinatorial complexity of set
systems. VC-dimension was first introduced in the context of statistical
learning theory, and is tightly related to the sample complexity in PAC
learning. VC-density is a refinement of VC-dimension. Both notions are also
studied in model theory, in the context of \emph{dependent} theories. A set
system that is definable by a formula of first-order logic with parameters has
finite VC-dimension if and only if the formula is a dependent formula.
  In this paper we study the VC-dimension and the VC-density of the edge
relation $Exy$ on Johnson graphs and on Hamming graphs. On a graph $G$, the set
system defined by the formula $Exy$ is the vertex set of $G$ along with the
collection of all \emph{open neighbourhoods} of $G$.
  We show that the edge relation has VC-dimension at most $4$ on Johnson graphs
and at most $3$ on Hamming graphs and these bounds are optimal.
  We furthermore show that the VC-density of the edge relation on the class of
all Johnson graphs is $2$, and on the class of all Hamming graphs the
VC-density is $2$ as well. Moreover, we show that our bounds on the
VC-dimension carry over to the class of all induced subgraphs of Johnson
graphs, and to the class of all induced subgraphs of Hamming graphs,
respectively. It also follows that the VC-dimension of the set systems of
\emph{closed neighbourhoods} in Johnson graphs and Hamming graphs is bounded.
  Johnson graphs and Hamming graphs are well known examples of distance
transitive graphs.
  Neither of these graph classes is nowhere dense nor is there a bound on their
(local) clique-width.
  Our results contrast this by giving evidence of structural tameness of the
graph classes.
