Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về độ dẫn của chuỗi Markov bậc
Tóm tắt
Giả sử Q là một khối lồi trong ℝn, được phân chia thành hai khối lượng u và v bởi một diện tích s. Chúng tôi chứng minh rằng s > min(u,v)/diam Q, và sử dụng bất đẳng thức này để thu được giới hạn dưới n-5/2 cho độ dẫn của các chuỗi Markov bậc, mô tả các bộ sinh gần như đồng nhất của các mở rộng tuyến tính cho các tập poset có kích thước n. Chúng tôi cũng thảo luận về một ứng dụng của kết quả trên đối với vấn đề sắp xếp các tập poset.
Từ khóa
Tài liệu tham khảo
F. Almgren (1976) Existence and regularity almost everywhere of solutions to elliptic variational problems with constraints, Mem. Amer. Math. Soc. No. 165.
G. Brightwell and P. Winkler (1990) Counting linear extensions is # P-complete. Preprint, Bellcore, July.
Yu. D.Burago and V. A.Zalgaller (1988) Geometric Inequalities, Berlin; New York, Springer-Verlag.
M. Dyer, A. Frieze, and R. Kannan (1988) A random polynomial time algorithm for estimating volumes of convex bodies. Preprint, Department of Computer Science, Carnegie-Mellon University, September.
M.Fredman (1976) How good is the information theory bound in sorting, Theoretical Computer Science 1, 355–361.
J. Kahn and M. Saks (1984) Every poset has a good comparison, Proc. 16-th Symposium on Theory of Computing, pp. 299–301.
A. Karzanov and L. Khachiyan (1990) On the conductance of order Markov chains. Technical Report DCS TR 268, Department of Computer Science, Rutgers University, June.
L. Lovasz and M. Simonovits (1990) The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. Preprint, Mathematical Institute of the Hungarian Academy of Sciences, May.
M. Mihail (1989) Conductance and convergence of Markov chain — A combinatorial treatment of expanders, Proc. 30-th Symp. on Foundations of Computer Science, pp. 526–531.
A. J.Sinclair and M. R.Jerrum (1989) Approximate counting generation and rapidly mixing Markov chains, Information and Computation 82, 93–133.
R. P.Stanley (1986) Two order polytopes, Discrete and Computational Geometry 1, 9–23.