VibeMathedMath problems solved by AI
All problems

Kannan–Tetali–Vempala conjecture (bipartite/binary-matrix case)

The swap chain flips checkerboard 2×2 blocks to sample 0/1 matrices with fixed row and column sums. Kannan, Tetali and Vempala conjectured in 1997 that it mixes in polynomial time for all feasible margins; the lazy chain is shown to have spectral gap at least (m2)−1(n2)−1\binom{m}{2}^{-1}\binom{n}{2}^{-1} on m×nm \times n matrices, which is worst-case tight and settles the bipartite case.

Result
Proved
Status
Resolved
AI contribution
AI-discovered
Method
Argument
Field
Markov chain mixing time
Posed by
Ravindran Kannan, Prasad Tetali, Santosh Vempala
Year posed
1997
Years open
29y
Solved
2026-06-21
Model
ChatGPT 5.5 Pro
Vendor
OpenAI
Collaborators
Weibo Fu (Princeton), Qian Qin (Minnesota), Guanyang Wang (Rutgers)
Verification
Lean-verified
Publication
Preprint
Significance
30 / 100
Disclosed cost
—
Wikipedia
No dedicated article

Sources

arxiv

Submitted by QuietLemur253

Changelog9 changes
  • Rasmus Lindahlchanged Statement from “We prove an explicit spectral-gap lower bound for the lazy swap chain on binary matrices w…” to “The swap chain flips checkerboard 2×2 blocks to sample 0/1 matrices with fixed row and col…”
  • Rasmus Lindahlchanged Statement from “We prove an explicit spectral-gap lower bound for the lazy swap chain on binary matrices w…” to “We prove an explicit spectral-gap lower bound for the lazy swap chain on binary matrices w…”
  • Rasmus Lindahlchanged Name from “Kannan–Tetali–Vempala conjecture” to “Kannan–Tetali–Vempala conjecture (bipartite/binary-matrix case)”
  • Rasmus Lindahlset Vendor to “OpenAI”
  • Rasmus Lindahlset Year posed to “1997”
  • Rasmus Lindahlset Posed by to “Ravindran Kannan, Prasad Tetali, Santosh Vempala”
  • Rasmus Lindahlset Collaborators to “Weibo Fu (Princeton), Qian Qin (Minnesota), Guanyang Wang (Rutgers)”
  • Rasmus Lindahlapproved this entry
  • QuietLemur253submitted this entry

Discussion