  Given $n$-vertex simple graphs $X$ and $Y$, the friends-and-strangers graph
$\mathsf{FS}(X, Y)$ has as its vertices all $n!$ bijections from $V(X)$ to
$V(Y)$, where two bijections are adjacent if and only if they differ on two
adjacent elements of $V(X)$ whose mappings are adjacent in $Y$. We consider the
setting where $X$ and $Y$ are both edge-subgraphs of $K_{r,r}$: due to a parity
obstruction, $\mathsf{FS}(X,Y)$ is always disconnected in this setting.
Modestly improving a result of Bangachev, we show that if $X$ and $Y$
respectively have minimum degrees $\delta(X)$ and $\delta(Y)$ and they satisfy
$\delta(X) + \delta(Y) \geq \lfloor 3r/2 \rfloor + 1$, then $\mathsf{FS}(X,Y)$
has exactly two connected components. This proves that the cutoff for
$\mathsf{FS}(X,Y)$ to avoid isolated vertices is equal to the cutoff for
$\mathsf{FS}(X,Y)$ to have exactly two connected components. We also consider a
probabilistic setup in which we fix $Y$ to be $K_{r,r}$, but randomly generate
$X$ by including each edge in $K_{r,r}$ independently with probability $p$.
Invoking a result of Zhu, we exhibit a phase transition phenomenon with
threshold function $(\log r)/r$: below the threshold, $\mathsf{FS}(X,Y)$ has
more than two connected components with high probability, while above the
threshold, $\mathsf{FS}(X,Y)$ has exactly two connected components with high
probability. Altogether, our results settle a conjecture and completely answer
two problems of Alon, Defant, and Kravitz.

Combinatorics;Discrete Mathematics