TY - JOUR

T1 - Typical and extremal aspects of friends-and-strangers graphs

AU - Alon, Noga

AU - Defant, Colin

AU - Kravitz, Noah

N1 - Funding Information:
The first author is supported in part by NSF grant DMS?1855464, BSF grant 2018267, and the Simons Foundation. The second author is supported by an NSF Graduate Research Fellowship (grant DGE?1656466) and a Fannie and John Hertz Foundation Fellowship. We are grateful to Kiril Bangachev for pointing out an error in an earlier proof of Lemma 5.2. We also thank the anonymous referee for several helpful suggestions.
Funding Information:
The first author is supported in part by NSF grant DMS–1855464 , BSF grant 2018267 , and the Simons Foundation . The second author is supported by an NSF Graduate Research Fellowship (grant DGE–1656466 ) and a Fannie and John Hertz Foundation Fellowship. We are grateful to Kiril Bangachev for pointing out an error in an earlier proof of Lemma 5.2 . We also thank the anonymous referee for several helpful suggestions.
Publisher Copyright:
© 2022 Elsevier Inc.

PY - 2022

Y1 - 2022

N2 - 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 σ:V(X)→V(Y), where two bijections σ and σ′ are adjacent if they agree everywhere except for two adjacent vertices a,b∈V(X) such that σ(a) and σ(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 Erdős-Rényi 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.

AB - 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 σ:V(X)→V(Y), where two bijections σ and σ′ are adjacent if they agree everywhere except for two adjacent vertices a,b∈V(X) such that σ(a) and σ(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 Erdős-Rényi 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.

KW - Connected graph

KW - Friends-and-strangers graph

KW - Minimum degree

KW - Random graph

UR - http://www.scopus.com/inward/record.url?scp=85126561361&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126561361&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2022.03.001

DO - 10.1016/j.jctb.2022.03.001

M3 - Article

AN - SCOPUS:85126561361

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -