Connectivity of friends-and-strangers graphs on random pairs (Q2111926)

Consider \(n\) people being placed in \(n\) positions. A move consists in exchanging the positions of two people, but it is valid only if they are friends, and in adjacent positions. If \(X\) denotes the ``friendship graph'', and \(Y\) denotes the graph modeling the positions, then the friends-and-strangers graph \(\mathrm{FS}(X,Y)\) is the graph whose vertices are the possible configurations of people (i.e.\ bijections \(\sigma:V(X)\to V(Y)\)) and whose edges are the valid moves between them. The article shows that \(\mathrm{FS}(X,Y)\) is connected with high probability if \(X\) and \(Y\) are independent Erdős-Rényi graphs \(X\sim \mathcal{G}(n,p_1)\), \(Y\sim \mathcal{G}(n,p_2)\), with \(p_1p_2 \geq p_0^2\) and \(\min(p_1,p_2)\geq 2p_0 / (\log n)^{1/3}\), where \(p_0=\exp(2(\log n)^{2/3})/n^{1/2}\). This result extends the symmetric case \(p_1=p_2\) which was studied by \textit{N. Alon} et al. [J. Comb. Theory, Ser. B 158, Part 1, 3--42 (2023; Zbl 1504.05146)]. The idea is to prove that with high probability, for every pair of vertices \(u,v\in V(Y)\) and every bijection \(\sigma:V(X)\to V(Y)\), there exists a finite sequence of valid moves from \(\sigma\) to \(\tau_{uv}\circ\sigma\), where \(\tau_{uv}\) is the transposition of \(u\) and \(v\). To show this, the authors show that with high probability one can embed two specific small sparse graphs \(G^\ast\) and \(H^\ast\) in \(X\) and \(Y\), whose structures ensure us that \(u\) and \(v\) can be exchanged from any \(\sigma\), in the sense described above.