Friends-and-Strangers FS(X,Y) isolated-vertex cutoff coincidence

Status solved high confidence

The conjecture asks whether $d_{r,r} = \lceil(3r+1)/4\rceil$ for all $r \equiv 1 \pmod{4}$, i.e., whether the cutoffs for $\mathrm{FS}(X,Y)$ to avoid isolated vertices and to have exactly two connected components coincide in this residue class. This was settled affirmatively by the paper arXiv:2309.03848 on bipartite friends-and-strangers graphs, whose Corollary 1.3 establishes $d_{r,r} = \lceil(3r+1)/4\rceil$ for all $r$ (including $r \equiv 1 \pmod{4}$), and explicitly states that this settles ADK Conjecture 7.4 (the journal-version numbering of the open question from arXiv:2009.07840). The same paper also proves, as a main theorem, that the two cutoffs are equal for all $r$.

Cited literature (1)

• proof Bipartite Friends and Strangers Walking on Bipartite Graphs (2023)
  not confirmed from fetch (see arXiv:2309.03848) · arXiv preprint (published Discrete Mathematics 2025) · arXiv:2309.03848

  Corollary 1.3 proves $d_{r,r} = \lceil(3r+1)/4\rceil$ for all $r$, and the main theorem proves that the cutoffs for $\mathrm{FS}(X,Y)$ to avoid isolated vertices and to have exactly two connected components coincide, thereby settling ADK Conjecture 7.4 (the conjecture from arXiv:2009.07840).

Reviewer notes. The open question appears as 'Open Question (§1.2, Theorem 1.4 remarks)' in the arXiv preprint and as 'Conjecture 7.4' in the published journal version ([ADK23]). arXiv:2309.03848 explicitly cites '[ADK23, Conjecture 7.4]' as what its Corollary 1.3 settles. Author names for 2309.03848 were not captured in the fetch responses; the URL https://arxiv.org/abs/2309.03848 was verified. The ScienceDirect journal version appeared in 2025 (pii/S0012365X25002754).

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