← All problems

The KTV conjecture on rapid mixing of switch Markov chains

7 years old · traced to

Let a switch Markov chain be the chain on realizations of a degree sequence that performs a switch, for an unconstrained, bipartite, or directed degree sequence. A degree sequence is graphic if it has at least one realization. The KTV conjecture. The switch Markov chain is rapidly mixing for any bipartite, directed, or unconstrained degree sequence. This conjecture concerns efficient nearly uniform sampling of graph realizations with prescribed degrees. Its general status is not specified in the source.

References
  1. Péter L. Erdős, Catherine Greenhill, Tamás Róbert Mezei, István Miklós, Dániel Soltész and Lajos Soukup, “The mixing time of the switch Markov chains: a unified approach”, arXiv:1903.06600 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. For every graphical labeled degree sequence of a simple undirected graph on n >= 4 vertices, the manuscript claims mixing time at total-variation distance 1/4 at most 2*n^8 for its lazy switch chain with uniformly proposed four-vertex switches. It also claims exact uniform sampling with polynomial expected bit time. This addresses the page’s unconstrained simple-undirected branch; bipartite and directed restrictions are not established here.See full solutionHide full solution