The Connectivity Threshold for Friends and Strangers graphs

Abstract

The concept of the Friends and Strangers graph $FS(G,H)$ associated with two graphs $G$ and $H$ was recently introduced by Defant and Kravitz and has generated significant interest. In a companion article, joint with Alon, they consider the behaviour of $FS(G,H)$ in the case where $G$ and $H$ are Erdős-Rényi random graphs, and prove that the threshold for connectivity is of the form $n^{-1/2+o(1)}$. In this paper we prove that the threshold is $n^{-1/2}\sqrt{\log{n}}$, up to a multiplicative constant, answering a question from Alon, Defant and Kravitz.