paper

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