  We initiate the study of property testing problems concerning relations
between permutations. In such problems, the input is a tuple
$(\sigma_1,\dotsc,\sigma_d)$ of permutations on $\{1,\dotsc,n\}$, and one
wishes to determine whether this tuple satisfies a certain system of relations
$E$, or is far from every tuple that satisfies $E$. If this computational
problem can be solved by querying only a small number of entries of the given
permutations, we say that $E$ is testable. For example, when $d=2$ and $E$
consists of the single relation $\mathsf{XY=YX}$, this corresponds to testing
whether $\sigma_1\sigma_2=\sigma_2\sigma_1$, where $\sigma_1\sigma_2$ and
$\sigma_2\sigma_1$ denote composition of permutations.
  We define a collection of graphs, naturally associated with the system $E$,
that encodes all the information relevant to the testability of $E$. We then
prove two theorems that provide criteria for testability and non-testability in
terms of expansion properties of these graphs. By virtue of a deep connection
with group theory, both theorems are applicable to wide classes of systems of
relations.
  In addition, we formulate the well-studied group-theoretic notion of
stability in permutations as a special case of the testability notion above,
interpret all previous works on stability as testability results, survey
previous results on stability from a computational perspective, and describe
many directions for future research on stability and testability.
