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.
Publisher Copyright:
© 2022 Elsevier Inc.

PY - 2023/1

Y1 - 2023/1

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

VL - 158

SP - 3

EP - 42

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -