Fix an element x of a finite partially ordered set P on n elements. Then let h"i(x) be the number of linear extensions of P in which x is in position i, counting from the bottom. The sequence {h"i(x):1@?i@?n} is the height sequence of x 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(x)h"i"+"2(x)@?h"i"+"1^2(x) 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.
['Csaba Biró', 'William T. Trotter']
A combinatorial approach to height sequences in finite partially ordered sets