Regular bipartite switch-connectivity threshold conjecture

From papers

Let GG be a dd-regular balanced bipartite graph on 2n2n vertices, and let f4d8k,regconnect(n)f4d8^{\mathbf{connect}}_{k,\mathrm{reg}}(n) denote the minimum-degree threshold for the kk-switch graph of such graphs to be connected. Regular switch-connectivity threshold conjecture. There exists c0c\geq 0 such that, for all nn and kk,

δk,regconnect(n)[2nk+1c,2nk+1+c].\delta^{\mathbf{connect}}_{k,\mathrm{reg}}(n)\in\left[\frac{2n}{k+1}-c,\frac{2n}{k+1}+c\right].

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 k=2k=2 and k=3k=3, while the lower bound is known when k+1k+1 divides nn.

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

No solutions have been posted yet.