Bangachev's connectivity conjecture for friends-and-strangers graphs
Let and be connected graphs on vertices, and let and denote their minimum degrees. Define to be the graph whose vertices are the bijections , with adjacent to if is obtained from by transposing two vertices such that and . If , then is connected.
References
- Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree — arXiv — Kai Mawhinney
Source: arXiv
Progress summary
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 vertices is connected, under a minimum-degree condition. The latest preprint claims that suffices.
Known results
- Alon, Defant, and Kravitz conjectured the threshold .
- Bangachev (2022) proved connectivity when additionally , together with the displayed degree inequality, and gave related disconnected examples.
- A 2021 paper obtained , matching the known lower bound up to an additive constant.
- Later work studies stronger -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 , and claims . 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.
Solutions 0
No solutions have been posted yet.