ON THE CONDUCTANCE OF ORDER MARKOV-CHAINS

被引：54

作者：

KARZANOV, A ^{[1
]}

KHACHIYAN, L ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,DEPT COMP SCI,NEW BRUNSWICK,NJ 08903

来源：

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 1991年 / 8卷 / 01期

关键词：

CONDUCTANCE; ISOPERIMETRIC INEQUALITY; LINEAR EXTENSION; POSET; UNIFORM GENERATION; SORTING;

D O I：

10.1007/BF00385809

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let Q be a convex solid in R(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.

引用

页码：7 / 15

页数：9

共 10 条

[1]

Almgren F. J., 1976, MEM AM MATH SOC, V165

[2]

BRIGHTWELL G, 1990, COUNTING LINEAR EXTE

[3]

Burago Y. D., 1988, GEOMETRIC INEQUALITI

[4]

DYER M, 1988, RANDOM POLYNOMIAL TI

[5]

Fredman M. L., 1976, Theoretical Computer Science, V1, P355, DOI 10.1016/0304-3975(76)90078-5

[6]

KAHN J, 1984, 16TH S THEOR COMP, P299

[7]

KARAZANOV A, 1990, DCS TR268 RUTGERS U

[8]

*LOVASZ L, 1990, MIXING RATE MARKOV C

[9]

MIHAIL M, 1989, 30 ANN S FDN COMPUTE, P526

[10]

STNALEY RP, 1986, DISCRETE COMPUTATION, V1, P9

← 1 →