Typical and extremal aspects of friends-and-strangers graphs

Given graphs X and Y with vertex sets V(X) and V(Y) of the same cardinality, the friends-and-strangers graph FS(X, Y ) is the graph whose vertex set consists of all bijections Sigma : V(X) -> V(Y), where two bijections Sigma and Sigma' are adjacent if they agree everywhere except for two adjacent vertices a, b is an element of V(X) such that Sigma(a) and Sigma(b) are adjacent in Y. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected; we address this problem from two different perspectives. First, we address the case of "typical" X and Y by proving that if X and Y are independent Erdos-Renyi random graphs with n vertices and edge probability p, then the threshold probability guaranteeing the connectedness of FS(X, Y) with high probability is p = n-1/2+o(1). Second, we address the case of "extremal" X and Y by proving that the smallest minimum degree of the n -vertex graphs X and Y that guarantees the connectedness of FS(X, Y ) is between 3n/5 +O (1) and 9n/14 +O (1). When X and Y are bipartite, a parity obstruction forces FS(X, Y ) to be disconnected. In this bipartite setting, we prove analogous "typical" and "extremal" results concerning when FS(X, Y ) has exactly 2 connected components; for the extremal question, we obtain a nearly exact result.(c) 2022 Elsevier Inc. All rights reserved.