Regular bipartite switch-connectivity threshold conjecture
Regular bipartite switch-connectivity threshold conjecture
Let be a -regular balanced bipartite graph on vertices, and let denote the minimum-degree threshold for the -switch graph of such graphs to be connected. Regular switch-connectivity threshold conjecture. There exists such that, for all and ,
The conjecture predicts that the connectivity threshold is within an additive constant of the degree of the cycle blow-up construction. The source notes that the upper bound is confirmed for and , while the lower bound is known when divides .
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ross J. Kang and Clément Legrand-Duchesne, “Dirac's theorem and the switch geometry of perfect matchings”, arXiv:2604.17911 (2026).
Additional references
2 papers in this index state this conjecture (2019–2026). The statement above is taken from the most recent of them; the others are arXiv:1906.12235.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.