The Connectivity Threshold for Friends and Strangers graphs

Source: arxiv.org/abs/2611.05254

Bruno Baldissera, Gabriel Dias do Couto, Simon Griffiths, Luiz Moreira

arXivarxiv/2611.05254Nov 3, 2026math.COscore 0

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.

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.05254
curl -X POST /api/v1/records/arxiv/2611.05254/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05254/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'