Mixing of binary-matrix swap chains with fixed margins
Follow the latest progress by email.
Does the lazy 2×2 swap chain mix in polynomial time for every feasible set of row and column sums of an m×n binary matrix, with m,n≥2? A precise target is spectral gap at least 1/[binom(m,2)binom(n,2)].
Why it matters and what counts as progress
Why it matters: Unrestricted margins are the remaining obstacle to a uniform sampling guarantee for fixed-degree bipartite incidence matrices.
What counts as progress: Prove a uniform gap or mixing bound for unrestricted margins, improve its dependence on m and n, or find a slow-mixing family.
How the problem developed
- 1997 · Conjecture [1]
Kannan, Tetali and Vempala Conjectured rapid mixing of the fixed-margin binary-matrix swap chain for every feasible choice of row and column sums.
- 21 Jun 2026 · Proof [1]
Weibo Fu, Qian Qin and Guanyang Wang, with the proof strategy and initial proofs generated by ChatGPT 5.5 Pro Proved a lazy-chain spectral-gap lower bound of 1/(binom(m,2) binom(n,2)) for every feasible m by n margin pair; the bound is worst-case tight and quantitatively strengthens the KTV conjecture.
AI contribution
Spectral Gap for the Binary Fixed-Margin Swap Chain
For every feasible set of row and column margins on an m×n binary matrix, with m,n≥2, the lazy 2×2 swap chain has spectral gap at least 1/[binom(m,2)binom(n,2)].
Sources
Website timeline
Publication dates and editorial changes.
AI-led proof of rapid mixing for fixed-margin binary matrices