Geometrical Techniques for Estimating Numbers of Linear Extensions
Geometrical Techniques for Estimating Numbers of Linear Extensions
复制标题
估计线性延伸数的几何技术
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Alexander Sidorenko
中科院分区：
文献类型：
--
作者：
B. Bollobás;G. Brightwell;Alexander Sidorenko
设P是一个二维阶，__Pany是P的补集，即任何其可比图是P的可比图的补的偏序。 Lete(Q)表示偏序Q的线性扩展的数量。 Sidorenko 证明对于任何二维偏序 P，e(P)e(__P) ?n!。在本文中，我们使用多面体组合学和 Rn 几何的结果来给出伴随上限 one(P)e(__P)，以及下界的替代证明。我们使用这些结果来获得随机二维偏序的线性扩展数量的界限。
LetPbe a two-dimensional order, and __Pany complement ofP, i.e., any partial order whose comparability graph is the complement of the comparability graph ofP. Lete(Q) denote the number of linear extensions of the partial orderQ. Sidorenko showed thate(P)e(__P) ?n!, for any two-dimensional partial orderP. In this note, we use results from polyhedral combinatorics, and from the geometry ofRn, to give a companion upper bound one(P)e(__P), as well as an alternative proof of the lower bound. We use these results to obtain bounds on the number of linear extensions of a random two-dimensional partial order.