## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 3-42 |

Number of pages | 40 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 158 |

DOIs | |

State | Published - Jan 2023 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Connected graph
- Friends-and-strangers graph
- Minimum degree
- Random graph