On the conductance of order Markov chains
On the conductance of order Markov chains
复制标题
关于阶马尔可夫链的电导
作者：
A. Karzanov;L. Khachiyan
设 Q 是 ℝn 中的凸立体，被面积 s 分为两个体积 u 和 v。我们证明 s>min(u,v)/diam Q，并使用这个不等式获得阶马尔可夫链电导的下界 n-5/2，它描述了大小为 n 的偏序集的几乎一致的线性扩展生成器。我们还讨论了上述结果在偏序集排序问题中的应用。
Let Q be a convex solid in ℝn, partitioned into two volumes u and v by an area s. We show that s>min(u,v)/diam Q, and use this inequality to obtain the lower bound n-5/2 on the conductance of order Markov chains, which describe nearly uniform generators of linear extensions for posets of size n. We also discuss an application of the above results to the problem of sorting of posets.