Inequalities for the number of linear extensions
Inequalities for the number of linear extensions
复制标题
线性延伸数不等式
DOI：
10.1007/bf00571183
复制
发表时间：
1991
期刊：
影响因子：
0.4
通讯作者：
Alexander Sidorenko
中科院分区：
文献类型：
--
作者：
Alexander Sidorenko
设\(e(P)\)表示偏序集\(P\)的线性扩张的数量。将\(P\)的哈斯图看作一个网络，并且将\(e(P)\)看作一个流的值，我们证明了\(e(P)\)的一些上界和下界。其中一个推论如下。如果\(P\)的不可比图能够被偏序集\(P_1\)，\(P_2\)，…，\(P_k\)的不可比图覆盖，那么\(e(P)\leq e(P_1)e(P_2)\cdots e(P_k)\)。
Lete(P) denote the number of linear extensions of a partial orderP. Interpreting the diagram ofP as a network, ande(P) as the value of a flow, we prove some upper and lower bounds fore(P). One of the consequences is the following. If the incomparability graph ofP can be covered by the incomparability graphs of ordersP1,P2,...,Pk thene(P) ≤e(P1)e(P2)...e(Pk).