TY - JOUR

T1 - Friends and strangers walking on graphs

AU - Alon, Noga

AU - Defant, Colin

AU - Kravitz, Noah

N1 - Funding Information:
∗nalon@math.princeton.edu. The author is supported by NSF grant DMS-1855464, BSF grant 2018267, and the Simons Foundation. †cdefant@princeton.edu. The author is supported by a Fannie and John Hertz Foundation Fellowship and NSF Graduate Research Fellowship grant DGE-1656466. ‡nkravitz@princeton.edu.
Publisher Copyright:
© 2021, Seminaire Lotharingien de Combinatoire. All Rights Reserved.

PY - 2021

Y1 - 2021

N2 - We introduce the friends-and-strangers graph FS(X,Y) associated with graphs X and Y whose vertex sets V(X) and V(Y) have the same cardinality. This 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. This setup, which has a natural interpretation in terms of friends and strangers walking on graphs, provides a common generalization of Cayley graphs of symmetric groups generated by transpositions, the famous 15-puzzle, generalizations of the 15-puzzle as studied by Wilson, and work of Stanley related to flag h-vectors. The most fundamental questions that one can ask about these friends-and-strangers graphs concern their connected components and, in particular, when there is only a single connected component. When X is a path graph, we show that the connected components of FS(X,Y) correspond to the acyclic orientations of the complement of Y. When X is a cycle, we obtain a full description of the connected components of FS(X,Y) in terms of toric acyclic orientations of the complement of Y. In a more probabilistic vein, 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). We also study 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). Furthermore, we obtain bipartite analogues of the latter two results.

AB - We introduce the friends-and-strangers graph FS(X,Y) associated with graphs X and Y whose vertex sets V(X) and V(Y) have the same cardinality. This 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. This setup, which has a natural interpretation in terms of friends and strangers walking on graphs, provides a common generalization of Cayley graphs of symmetric groups generated by transpositions, the famous 15-puzzle, generalizations of the 15-puzzle as studied by Wilson, and work of Stanley related to flag h-vectors. The most fundamental questions that one can ask about these friends-and-strangers graphs concern their connected components and, in particular, when there is only a single connected component. When X is a path graph, we show that the connected components of FS(X,Y) correspond to the acyclic orientations of the complement of Y. When X is a cycle, we obtain a full description of the connected components of FS(X,Y) in terms of toric acyclic orientations of the complement of Y. In a more probabilistic vein, 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). We also study 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). Furthermore, we obtain bipartite analogues of the latter two results.

KW - acyclic orientation

KW - friends-and-strangers graph

KW - toric acyclic orientation

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

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

M3 - Article

AN - SCOPUS:85161317665

SN - 1286-4889

JO - Seminaire Lotharingien de Combinatoire

JF - Seminaire Lotharingien de Combinatoire

IS - 85

M1 - #21

ER -