任意图度序列下交换链的多项式混合
Polynomial mixing of the switch chain for every graphical degree sequence
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究 Kannan–Tetali–Vempala 猜想中简单无向图的情形。作者声称，对每个图度序列，简单无向图上的交换链都在多项式时间内混合；对在四个顶点上均匀提议交换的惰性链，距离 1/4 的总变差混合时间至多 2n⁸。摘要还称给出对每个图度向量的精确均匀采样器，使用无偏随机比特、几乎必然终止，且期望比特运行时间为多项式。
- 声称证明交换链对每个图度序列都在多项式时间内混合。
- 惰性链在距离 1/4 处的总变差混合时间上界为 2n⁸。
- 另给出精确均匀采样器，使用无偏随机比特且期望多项式比特时间。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove the simple-undirected form of the Kannan–Tetali–Vempala conjecture: the switch chain on simple undirected graphs mixes in polynomial time for every graphical degree sequence. For a lazy chain that proposes switches uniformly on four vertices, the total-variation mixing time at distance 1/4 is at most $`2n^8`$. We also give an exactly uniform sampler for every graphical labeled degree vector. It uses unbiased random bits, terminates almost surely, and has expected polynomial bit running time.
用户标记：未标记
固定编号：4235ff18c278881a
原文来源