← All problems

Bangachev's connectivity conjecture for friends-and-strangers graphs

Let XX and YY be connected graphs on nn vertices, and let δ(X)\delta(X) and δ(Y)\delta(Y) denote their minimum degrees. Define FS(X,Y)\mathrm{FS}(X,Y) to be the graph whose vertices are the bijections σ:V(X)→V(Y)\sigma:V(X)\to V(Y), with σ\sigma adjacent to σ′\sigma' if σ′\sigma' is obtained from σ\sigma by transposing two vertices a,b∈V(X)a,b\in V(X) such that ab∈E(X)ab\in E(X) and σ(a)σ(b)∈E(Y)\sigma(a)\sigma(b)\in E(Y). If 2min⁡{δ(X),δ(Y)}+3max⁡{δ(X),δ(Y)}≥3n2\min\{\delta(X),\delta(Y)\}+3\max\{\delta(X),\delta(Y)\}\ge 3n, then FS(X,Y)\mathrm{FS}(X,Y) is connected.

References

Progress summary

Refreshed
Open · solution reported

A preprint from October 2026 claims to prove the conjectured connectivity rule and gives a matching travel-distance bound, but the claim has not been independently checked.

The conjecture concerns when the friends-and-strangers graph formed from two graphs on nn vertices is connected, under a minimum-degree condition. The latest preprint claims that 2min⁡{δ(X),δ(Y)}+3max⁡{δ(X),δ(Y)}≥3n2\min\{\delta(X),\delta(Y)\}+3\max\{\delta(X),\delta(Y)\}\ge 3n suffices.

Known results

  • Alon, Defant, and Kravitz conjectured the threshold dn=35n+O(1)d_n=\frac{3}{5}n+O(1).
  • Bangachev (2022) proved connectivity when additionally δ(X),δ(Y)>n/2\delta(X),\delta(Y)>n/2, together with the displayed degree inequality, and gave related disconnected examples.
  • A 2021 paper obtained dn≤⌈3n/5⌉d_n\le\lceil 3n/5\rceil, matching the known lower bound up to an additive constant.
  • Later work studies stronger kk-connectivity but does not independently establish the new general claim.

October 2026 claimed resolution

Kai Mawhinney’s preprint claims the degree inequality alone implies connectivity for connected X,YX,Y, and claims diam⁡(FS(X,Y))=O ⁣(n2/min⁡{δ(X),δ(Y)})\operatorname{diam}(\mathrm{FS}(X,Y))=O\!\left(n^2/\min\{\delta(X),\delta(Y)\}\right). No independent assessment, correction, withdrawal, or refutation was found.

Current status (as of October 2026): Earlier stronger-condition results are established, while the unrestricted degree-condition theorem and diameter bound remain an unverified claim.

Sources

Solutions 0

No solutions have been posted yet.