{"id":"arxiv/2611.05254","url":"https://arxiv.org/abs/2611.05254","tags":["math.CO"],"score":0,"title":"The Connectivity Threshold for Friends and Strangers graphs","domain":"math.CO","source":"arxiv","authors":["Bruno Baldissera","Gabriel Dias do Couto","Simon Griffiths","Luiz Moreira"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}