The Connectivity Threshold for Friends and Strangers graphs
arXiv:2611.05254
Abstract
The concept of the Friends and Strangers graph associated with two graphs and was recently introduced by Defant and Kravitz and has generated significant interest. In a companion article, joint with Alon, they consider the behaviour of in the case where and are Erdős-Rényi random graphs, and prove that the threshold for connectivity is of the form . In this paper we prove that the threshold is , up to a multiplicative constant, answering a question from Alon, Defant and Kravitz.
arXiv comment23 pages