A combinatorial approach to height sequences in finite partially ordered sets

作者：Biro Csaba^*; Trotter William T

来源：Discrete Mathematics, 2011, 311(7): 563-569.

DOI：10.1016/j.disc.2010.12.020

• Correlation inequality
• Height sequence
• Log-concavity

Fix an element chi of a finite partially ordered set P on n elements. Then let h(i)(chi) be the number of linear extensions of P in which x is in position i, counting from the bottom. The sequence {h(i)(chi) : 1 <= i <= n} is the height sequence of chi in P. In 1982, Stanley used the Alexandrov-Fenchel inequalities for mixed volumes to prove that this sequence is log-concave, i.e., h(i)(chi)h(i+2)(chi) <= h(i+1)(2)(chi) for 1 <= i <= n - 2. However, Stanley's elegant proof does not seem to shed any light on the error term when the inequality is not tight; as a result, researchers have been unable to answer some challenging questions involving height sequences in posets. In this paper, we provide a purely combinatorial proof of two important special cases of Stanley's theorem by applying Daykin's inequality to an appropriately defined distributive lattice. As an end result, we prove a somewhat stronger result, one for which it may be possible to analyze the error terms when the log-concavity bound is not tight.

• 出版日期2011-4-6