Isolated-vertex threshold for FS(X,Y) connectivity

Informal Conjecture (§1.2, Theorem 1.1 remarks) · arXiv:2009.07840

arXiv Informal medium confidence— first stated 2021-06-15

Authors: Noga Alon, Colin Defant, Noah Kravitz

Status partial medium confidence

Three follow-up papers have narrowed the gap in Theorem 1.1 of the source paper. Milojevic (arXiv:2210.03864, 2022) improved the isolated-vertex lower bound and disproved two formal conjectures from the source paper about threshold probabilities. Krishnan and Li (arXiv:2410.21334, 2024) established k-connectivity for p ≥ n^{-1/2+o(1)}, bringing the connectivity upper bound and isolated-vertex lower bound to the same asymptotic order n^{-1/2+o(1)}, broadly consistent with the informal conjecture. A sharp threshold matching an exact constant has not been proved.

Cited literature (3)

partial Connectivity of friends-and-strangers graphs on random pairs (2022)

Lanchao Wang, Yaojun Chen · Discrete Mathematics · arXiv:2208.00801

Extends the connectivity threshold analysis to the asymmetric case X ∈ G(n,p₁), Y ∈ G(n,p₂), showing FS(X,Y) is connected with high probability when p₁p₂ ≥ n^{-1+o(1)}, consistent with the isolated-vertex-threshold heuristic.
partial Connectivity of Old and New Models of Friends-and-Strangers Graphs (2022)

Aleksa Milojevic · arXiv preprint · arXiv:2210.03864

Slightly improves the isolated-vertex lower bound on the disconnectedness threshold for FS(X,Y) when X,Y ∼ G(n,p), showing isolated vertices persist up to p = O(log n / n^{1/2}), and in doing so disproves two formal conjectures of Alon, Defant, and Kravitz about specific threshold probabilities.
partial On the Connectivity of Friends-and-strangers Graphs (2024)

Neil Krishnan, Rupert Li · arXiv preprint · arXiv:2410.21334

Shows that for independent G(n,p₁) and G(n,p₂) with p₁p₂ ≥ p₀² where p₀ = n^{-1/2+o(1)}, FS(X,Y) is k-connected with high probability, improving the connectivity upper bound in the symmetric case to the same n^{-1/2+o(1)} order as the isolated-vertex threshold.

Reviewer notes. The two formal conjectures disproved by Milojevic (arXiv:2210.03864) appear to be distinct formal conjectures in the source paper about specific threshold values, not the informal conjecture reviewed here; the full paper text could not be retrieved so the exact disproved statements are unconfirmed. The informal conjecture (connectivity threshold determined by isolated-vertex threshold) is broadly consistent with current bounds — both lower and upper bounds now sit at n^{-1/2+o(1)} — but the sharp threshold with an exact constant matching the isolated-vertex threshold has not been established.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. The threshold for $\mathrm{FS}(X, Y)$ to be connected when $X, Y \sim G(n,p)$ is determined by the isolated-vertex threshold: ``it seems that (as in the usual case of a binomial random graph) this local obstruction to connectedness tells essentially the whole story.''

Context

Theorem 1.1 establishes a lower bound $p \leq (2^{-1/2}-\varepsilon)/n^{1/2}$ arising from isolated vertices and an upper bound $p \geq \exp(2(\log n)^{2/3})/n^{1/2}$ for the high-probability connectivity threshold of $\mathrm{FS}(X,Y)$. The authors suggest the gap between these bounds is an artifact of the proof method and that the two thresholds should coincide up to lower-order factors.

Notes. PDF source; prose conjecture without a labelled environment. Section 7 (explicitly titled as containing open questions and conjectures) is absent from the supplied text, so further items from that section could not be extracted.

Source paper

Typical and Extremal Aspects of Friends-and-Strangers Graphs
Noga Alon, Colin Defant, Noah Kravitz · 2021-06-15
https://arxiv.org/abs/2009.07840 PDF source