  We study a family of random permutation models on the Hamming graph $H(2,n)$
(i.e., the $2$-fold Cartesian product of complete graphs), containing the
interchange process and the cycle-weighted interchange process with parameter
$\theta > 0$. This family contains the random walk representation of the
quantum Heisenberg ferromagnet. We show that in these models the cycle
structure of permutations undergoes a \textit{phase transition} -- when the
number of transpositions defining the permutation is $\leq c n^2$, for small
enough $c > 0$, all cycles are microscopic, while for more than $\geq C n^2$
transpositions, for large enough $C > 0$, macroscopic cycles emerge with high
probability.
  We provide bounds on values $C,c$ depending on the parameter $\theta$ of the
model, in particular for the interchange process we pinpoint exactly the
critical time of the phase transition. Our results imply also the existence of
a phase transition in the quantum Heisenberg ferromagnet on $H(2,n)$, namely
for low enough temperatures spontaneous magnetization occurs, while it is not
the case for high temperatures.
  At the core of our approach is a novel application of the cyclic random walk,
which might be of independent interest. By analyzing explorations of the cyclic
random walk, we show that sufficiently long cycles of a random permutation are
uniformly spread on the graph, which makes it possible to compare our models to
the mean-field case, i.e., the interchange process on the complete graph,
extending the approach used earlier by Schramm.
