.^{1}

Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry: an update

FRANCESCO BRENTI

1 Introduction

Log-concave and unimodal sequences arise often in combinatorics, algebra, geometry and computer science, as well as in probability and statistics where these concepts were first defined and studied. Even though log-concavity and unimodality have one-line definitions, it has now become apparent that to prove the unimodality or log-concavity of a sequence can sometimes be a very difficult task requiring the use of intricate combinatorial constructions or of refined mathematical tools. The number and variety of these tools has been constantly increasing and is quite bewildering and surprising. They include, for example, classical analysis, linear algebra, the representation theory of Lie algebras and superalgebras, the theory of total positivity, the theory of symmetric functions, and algebraic geometry.

In [51] R. Stanley gave an excellent survey of many of these techniques, problems, and results. Since then (the paper had been written in the Spring of 1986) new techniques have been developed, many new results have been obtained and some of the problems have been solved, while new ones have emerged. Our purpose in this paper is to give a survey of these developments.

11991 Mathematics Subject Classification. Primary 22A05, 73K12; Secondary 23axx.

The author was partially supported by EC grant No. CHRX-CT93-0400.

This paper is in final form and no version of it will be submitted for publication elsewhere.

.

Sections 2 through 7 of the present paper have the same title as corresponding sections of [51] and are intended to supplement and update the material in them. Two of the sections in [51] (namely, “Representations of sl(2; C)” and “A Final Word of Warning”) have no corresponding section in the present paper because we have nothing to add to them. Section 8 (“Total positivity”) covers a new technique for attacking unimodality problems that was in its infancy at the time of the writing of [51] and which, therefore, is not covered there. In each one of the next 6 sections we assume that the reader is familiar with (and can refer to) the corresponding section of [51]. Of course, it is impossible to cover all work done in unimodality since the publishing of [51], and we make no claims in this direction.

Throughout this paper we follow [50] for standard combinatorial notation and terminology (including partially ordered sets) and we follow [29] for symmetric functions notation and terminology.

A sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d−1. It is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j − 1 and a_{i} ≥ a_{i+1} for i = j, …, d − 1. It is said to have no internal zeros if there are not three indices 0 ≤ i < j < k ≤ d such that a_{i}, a_{k} ≠ 0 and a_{j} = 0. It is said to be symmetric if a_{i} = a_{d−i} for i = 0, …, ⌊\frac{d}{2}⌋. We say that a polynomial ∑_{i=0}^{d} a_{i} x^{i} is logconcave (respectively, unimodal, with no internal zeros, symmetric) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} t^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal, with no internal zeros (see, e.g., [14], Thm. B, p.270). If p(x) is a symmetric unimodal polynomial then there is a unique n ∈ N such that x^{n} p (\frac{1}{x}) = p (x). We call the number \frac{n}{2} the center of symmetry of p (x), and we write C(p) = \frac{n}{2}.

2 Direct Combinatorial Methods

Direct combinatorial methods to prove that a sequence is log-concave or unimodal have been used often since the publishing of [51]. In particular, direct combinatorial proofs of the log-concavity of the Stirling numbers of both kinds appear in [42] where more general arrays of numbers are treated with a unified technique. This technique consists of encoding the given sequence by means of paths in a directed graph, and then using the geometry of the digraph to construct an appropriate injection. This visualization makes it a lot easier to construct the desired injections, and usually makes them more intuitive. For example, the strange looking injection for the binomial coefficients given in [51], p. 501, has a very simple geometric meaning (see [42], §4).

In this respect, we should mention a conjecture which would generalize the unimodality of the binomial coefficients and which seems particularly suited to be attacked by combinatorial techniques. Given n, m ∈ P let [n] × [m] be the direct product (as a poset) of the two chains [n] and [m] (ordered in the natural way). Then, of course, α([n + 1] × [m + 1]) = (\begin{matrix}n+m \\ m \end{matrix}) (where α(P) denotes the number of all maximal chains of the poset P), and therefore the sequence

{α([n + 1] × [1]), α([n] × [2]), α([n − 1] × [3]), …, α([1] × [n + 1])}

is unimodal, being the sequence of binomial coefficients. Now let λ = (λ_{1}, λ_{2}, …, λ_{m}) be a partition into at most m parts with largest part ≤ n, and let D(n + 1, m + 1; λ) be the subposet of [n + 1] × [m + 1] induced by {(i, j) ∈ [n + 1] × [m + 1] : i ≤ n + 1 − λ_{j} for j = 1, …, m + 1} (where λ_{m+1} =^{def} 0). For example, the Hasse diagram of D(3, 4, (2, 2, 1)) is shown in Figure 1.

[figure]

Figure 1: the Hasse diagram of D(3, 4; (2, 2, 1)).

Then R. Simion (private communication, 1/92) conjectures the following.

Conjecture 2.1 Let λ = (λ_{1}, …, λ_{r}) be a partition and n ∈ P be such that n ≥ r + λ_{1}. Then the sequence {α(D(n + 2 − k, k; λ))}_{k=r+1,r+2,...,n+1−λ_{1}} is unimodal.

Stanley mentioned in [51], p. 501, that the sequence of q-binomial coeffi-

cients \{[\begin{matrix}n \\ k \end{matrix}]_{q}\}_{k=0,...,n} is log-concave for all q ≥ 0. This observation spurred

research in several directions and led to the concepts of q-log-concavity and q-unimodality, which were first defined by Stanley (see [44], p. 795), and first studied by Butler, Krattenthaler, Leroux, and Sagan (see, [13], [24], [27], [43], [44]). A sequence of polynomials {f_{i}(q)}_{i=0,...,d} ⊆ R[q] is said to be q-log-concave if f_{i}^{2}(q) − f_{i−1}(q)f_{i+1}(q) has nonnegative coefficients for i = 1, …, d − 1, and q-unimodality is defined similarly. Clearly, q-log-concavity implies log-concavity for all q ≥ 0. However, it is not hard to see that q-log-concavity does not imply q-unimodality (see, e.g., [43], p. 300). Direct combinatorial methods have been used successfully to prove that several sequences of q-Stirling numbers of both kinds and of q-binomial coefficients are indeed q-log-concave, ([10], [13], [24], [27], [44]). The following is a typical example of the results that have been obtained with these methods (we refer the reader to, e.g., [44], p. 796, for the definition of the q-Stirling numbers c[n, k]_{q} and S[n, k]_{q}).

Theorem 2.2 Let n ∈ P. Then the sequences \{[\begin{matrix}n \\ k \end{matrix}]_{q}\}_{k=0,...,n}, \{c[n, k]_{q}\}_{k=0,...,n},

and {S[n, k]_{q}}_{k=0,...,n} are q-log-concave.

The preceding theorem actually embodies different results due to different authors (see [13], Theorem 4.2, [24], [27], Theorems 2.1 and 4.2, [43], Theorems 2.3, 2.4, and 2.5).

A further application of direct combinatorial methods to log-concavity problems appears in [4], Theorem 7.6.5. Let (P, ω) be a labeled poset. For s ∈ N let Ω((P, ω); s) be the number of (P, ω)-partitions with largest part ≤ s (see, e.g., [46], §2, p. 5 for the definition and further information about (P, ω)-partitions).

Theorem 2.3 Let (P, ω) be a labeled poset. Then the sequence {Ω((P, ω); s)}_{s∈N} is log-concave.

The preceding result was first proved in the case of a natural labeling in [16] and then in the general case in [4], Chapter 7, §6, using appropriate injections.

Even though direct combinatorial methods have been quite successful in some areas there are many other cases in which combinatorial proofs of unimodality seem to be extremely difficult to find. Aside from the (by now) classical case of the unimodality of the Gaussian polynomials (finally settled in [34], see also [60]), another (quite complicated) combinatorial proof of a unimodality result was recently given by J. Stembridge in [54]. By encoding permutations using a certain bijection (too complicated to be explained here) Stembridge is able to construct an injection which shows combinatorially that A(n, k) ≤ A(n, k + 1) if 1 ≤ k ≤ ⌈\frac{n}{2}⌉ − 1, where A(n, k) is an Eulerian number (i.e., A(n, k) =^{def} |{σ ∈ S_{n} : σ has k −1 descents }|). Since it is easily seen that A(n, k) = A(n, n + 1 − k) this gives the first combinatorial proof of the fact that Eulerian polynomials are unimodal (all other known proofs use either analytic tools, such as those discussed in the next section, or the theory of symmetric functions).

As mentioned in [51], p. 501, the problem of proving the unimodality of

[\begin{matrix}n \\ k \end{matrix}]_{q} is much more difficult than that of showing that \{[\begin{matrix}n \\ k \end{matrix}]_{q}\}_{k=0,...,n} is a log-

concave sequence for q ≥ 0 (or even q-log-concave). A similar phenomenon seems to occur also for the q-Stirling numbers. In fact, we have the following conjectures.

Conjecture 2.4 Let n ∈ P and k ∈ [n]. Then the polynomial S[n, k]_{q} is log-concave.

Conjecture 2.5 Let n ∈ P and k ∈ [n]. Then the polynomial c[n, k]_{q} is log-concave.

Conjecture 2.4 was first stated in [56], while Conjecture 2.5 appears in [27], (see Conjecture 4.6). Both conjectures have been verified for n ≤ 20.

Inductive proofs of unimodality and log-concavity have also been used extensively since the appearance of [51]. For example, the proof of Theorem 2.2 appearing in [43] is inductive. Also, the results of [42] are proved inductively (see §2 of [42]) as well as combinatorially. A particularly interesting example of an inductive proof of unimodality was given by F. Regonati in [37]. Using a completely elementary and combinatorial inductive procedure Regonati proves the following remarkable result.

Theorem 2.6 Let L be a finite modular lattice. Then the following are equivalent:

i) L is rank symmetric and unimodal;

ii) every interval of L of rank 3 is rank symmetric (and unimodal).

As noted in [37] the preceding result implies as a special case Theorem 1 of [51], thus giving it an elementary proof that avoids completely the deep results from the theory of symmetric functions that were used in the original proof (see [12]). Incidentally, we should note that an inductive, elementary proof of Theorem 1 of [51] had already been given by F. Regonati in [36]. This proof was obtained independently from (and at about the same time as) Butler’s proof ([12]).

Another example of an inductive proof of unimodality appears in [19], where the principal specialization of any Schur function is shown to be unimodal as a consequence of a deep polynomial identity involving q-binomial coefficients.

Section 2 of [51] concluded with a discussion of some operations on sequences that preserve the unimodality and/or log-concavity properties. Since the publishing of [51] such operations have been greatly studied and many new results have been found. Since these results are not proved by combinatorial methods, but by using the theory of total positivity, we discuss them separately in section 8.

3 Polynomials with Real Zeros

Since the appearance of [51] several new techniques for showing that a polynomial has only real zeros have been developed (or, sometimes, rediscovered from old classical analysis books) and applied to combinatorial problems. We now describe the most significant ones.

An infinite matrix M = (M_{n,k})_{n,k∈N} is totally positive (or T P, for short) if all minors of M have nonnegative determinant. A sequence {a_{i}}_{i∈N} is a Pólya frequency sequence (or a P F sequence, for short) if the matrix A =^{def} (a_{n−k})_{n,k∈N} (where a_{i} =^{def} 0 if i < 0) is T P. A finite sequence {a_{0}, a_{1}, …, a_{d}} is P F if the sequence {a_{0}, a_{1}, …, a_{d}, 0, 0, …} is P F. These concepts arose first in statistics and probability, and the standard reference for them is [23]. Note that a P F sequence is necessarily log-concave. Theorem 3.1 Let ∑_{i=0}^{d} a_{i}x^{i} ∈ R[x] and suppose that a_{i} ≥ 0 for i = 0, …, d. Then ∑_{i=0}^{d} a_{i}x^{i} has only real zeros if and only if {a_{0}, a_{1}, …, a_{d}} is a P F sequence.

The preceding theorem was first proved by Edrei in [17], and we refer the reader to [4], §4.5, and [23], p. 412, Theorem 5.3, for its proof (the “if” statement is the hard part of it). To get an appreciation of the depth and power of this result the reader should prove it for d = 2.

Let us mention a combinatorial application of Theorem 3.1. For n, r ∈ P let D_{r}(n) be the set of all permutations σ ∈ S_{n} such that all the cycles of σ have size ≥ r. So D_{1}(n) = S_{n}, and D_{2}(n) is the set of derangements of S_{n}. For σ ∈ S_{n} let c(σ) be the number of cycles of σ. By interpreting combinatorially the appropriate minors and then using Theorem 3.1 the following result is proved in [10] (see Corollary 5.9).

Theorem 3.2 Let n ∈ P and r ∈ [n]. Then the polynomial

∑_{σ∈D_{r}(n)} x^{c(σ)}

has only real zeros.

For r = 1 the preceding result is well known (see, e.g., [50], Proposition 1.3.4), while for r = 2 it was first proved by R. Canfield (private communication) using analytic techniques.

Of course, only the 2 × 2 minors are needed to prove the log-concavity of a polynomial. Nonetheless, it can be of combinatorial interest to know “what the minors count” even when one already knows that they are nonnegative. For example, it is well known (see, e.g., [14], p. 292, Exercise 3) that the Eulerian polynomials have only real zeros, but no combinatorial interpretation of the numbers

det [ \begin{matrix}A_{n,i} & A_{n,i+1} & … & A_{n,i+r} \\ A_{n,i−1} & A_{n,i} & … & A_{n,i+r−1} \\ ⋮ & ⋮ & & ⋮ \\ A_{n,i−r} & A_{n,i−r+1} & … & A_{n,i} \end{matrix} ] (1)

(where A_{n,k} =^{def} 0 if k < 0), is known at present. Since nice answers have been found for the corresponding (and other) minors formed with various combinatorial numbers and polynomials (see [7], [10], and [44], §5), and since a general combinatorial interpretation (though slightly abstract) exists for the minors of any T P matrix (see, [10], Theorem 3.5) it is conceivable that (1) should have a natural combinatorial meaning.

Another classical analysis result which can be used to prove that a polynomial has only real zeros is the following.

Theorem 3.3 Let ∑_{i=0}^{d} a_{i}x^{i}, ∑_{i=0}^{c} b_{i}x^{i} ∈ R[x] be two polynomials having nonnegative coefficients and only real zeros. Then ∑_{i≥0} i! a_{i}b_{i}x^{i} (where a_{i} =^{def}

0 if i > d and b_{i} =^{def} 0 if i > c) has only real zeros.

The preceding theorem was first proved by Schur (see [45]). A proof of it can be found in [28], Chapter VIII, §2 (see also Problem 156 in Part V of Vol. II of [35]). Theorem 3.3 is so easy to use that no applications of it alone exist to combinatorial problems. Rather, it can be used as a routine ingredient in more elaborate proofs.

Some recent results which have been obtained for proving that a polynomial has only real zeros are the following. For i ∈ P we let (x)_{i} =^{def} x(x − 1) … (x − i + 1), ⟨x⟩_{i} =^{def} (−1)^{i}(−x)_{i}, and (x)_{0} =^{def} ⟨x⟩_{0} =^{def} 1.

Theorem 3.4 Let ∑_{i=0}^{d} c_{i}x^{i} be a polynomial with nonnegative coefficients and only real zeros. Then the polynomial ∑_{i=0}^{d} c_{i}⟨x⟩_{i} has only real zeros.

Theorem 3.5 Let ∑_{i=0}^{d} a_{i}(x)_{i} be a polynomial with nonnegative coefficients and only real zeros. Then ∑_{i=0}^{d} a_{i}x^{i} has only real zeros.

Both these results (which are actually not best possible) are proved by induction using analytic techniques, (see Theorems 2.4.2 and 2.4.3 of [4], for the proofs).

For a combinatorial application of Theorem 3.4 consider (for n ∈ P and k ∈ [n]) the number b(n, k) of functions from [n] to itself whose functional digraph has exactly k connected components. It is then well known (see, e.g., [20], ex. 3.3.28, p. 192) that

b(n, k) = ∑_{i=1}^{n} (\begin{matrix}n−1 \\ i−1 \end{matrix}) n^{n−i}c(i, k) ,

(where c(i, k) denotes, as usual, a signless Stirling number of the first kind). Hence

∑_{k=1}^{n} b(n, k)x^{k} = ∑_{i=1}^{n} (\begin{matrix}n−1 \\ i−1 \end{matrix}) n^{n−i}⟨x⟩_{i} .

But ∑_{i=1}^{n} (\begin{matrix}n−1 \\ i−1 \end{matrix}) n^{n−i}x^{i} = x(x+n)^{n−1} has only real zeros, therefore we obtain from Theorem 3.4 the following result which was first noted in [4], §6.4.

Proposition 3.6 Let n ∈ P. Then the polynomial ∑_{k=1}^{n} b(n, k)x^{k} has only real zeros. In particular, it is log-concave and unimodal.

An operation that is performed frequently on polynomials (especially in combinatorics), is that of taking the generating function of its values at nonnegative integers. It is well known (see, e.g., [50], Corollary 4.3.1) that this is always a rational generating function. More precisely, given f(x) ∈ R[x] there exists a unique w(x) ∈ R[x] (called the f-Eulerian polynomial, see [50], p. 209) such that

∑_{n≥0} f(n)x^{n} = \frac{w(x)}{(1 − x)^{d+1}}

in R[[x]], where d = deg(f). It is therefore natural to look for properties of f(x) that imply that w(x) has only real zeros. Motivated by Conjecture 1 of [51] much work has been done in this direction, and the following are two of the main results that have been obtained. Given a polynomial f ∈ R[x] having only real zeros we denote by λ(f) (respectively, Λ(f)) the smallest (respectively, largest) zero of f.

Theorem 3.7 Let f(x) ∈ R[x] and w(x) be the f-Eulerian polynomial. Suppose that f(x) has only real zeros and that f(x) = 0 for all x ∈ ([λ(f), −1]∪ [0, Λ(f)]) ∩ Z. Then w(x) has nonnegative coefficients and only real zeros.

Theorem 3.8 Let f(x), g(x) ∈ R[x] and w(x), v(x) be the f-Eulerian and g-Eulerian polynomials, respectively. Suppose that w(x) and v(x) both have nonnegative coefficients and only real zeros, then the (fg)-Eulerian polynomial also does.

Both these results are proved by analytic techniques and we refer the reader to [4], Theorem 4.4.1, and [57], Theorem 0.3, for their proofs. Theorems 3.7 and 3.8 have found numerous applications to combinatorics, especially to the problems that originally motivated them. We discuss these problems and applications next.

The conjectures appearing in section 3 of [51] are all still open. However, a host of related conjectures have appeared in the literature, and some partial results have been obtained.

Conjecture 1 of [51] has been generalized by R. Stanley (private communication, 11/86) to any labeled poset. More precisely, let P be a finite poset of size p and ω : P → [p] a bijection (i.e. a labeling of P). For an order preserving bijection τ : P → [p] (i.e. a natural labeling of P) we let

d(τ, ω) =^{def} |{i ∈ [p − 1] : ω(τ^{−1}(i)) > ω(τ^{−1}(i + 1))}|.

Conjecture 3.9 For any finite poset P and labeling ω of P the polynomial

W ((P, ω); x) =^{def} ∑_{τ} x^{d(τ,ω)} (2)

has only real zeros (where the sum is over all natural labelings τ of P).

Conjecture 1 of [51] is obtained by taking ω to be a natural labeling. Conjecture 3.9 is open even for the unimodality statement. J. Stembridge (private communication) has (developed and) used a Maple package for handling posets to verify Conjecture 3.9 for any P of size ≤ 7 in the case of a natural ω. Conjecture 3.9 is known to be true for labeled disjoint unions of chains, naturally labeled Gaussian posets, column strict labeled Ferrers posets, naturally labeled Ferrers posets of shape λ = (λ_{1}, …, λ_{r}) with λ_{i} − λ_{i+1} = λ_{i+1} − λ_{i+2} for i = 1, …, r − 2, and labeled series-parallel posets (see [4], Chapter 5, and [58], p. 320, for the definitions of these posets and proofs of these statements). Note that all these partial results on Conjecture 3.9 have been obtained by applying Theorems 3.7 and 3.8 to known formulas for the polynomial W ((P, ω); x) (or, more precisely, Ω((P, ω); x)) of these classes of posets. It is not hard to see that if Conjecture 3.9 holds for two labeled posets (P_{1}, ω_{1}) and (P_{2}, ω_{2}) then it also holds for their labeled direct sum (P_{1} ⊕ P_{2}, ω_{1} ⊕ ω_{2}) (see [4], Proposition 1.3.1). One of the deepest contributions to Conjecture 3.9 (and an easy consequence of Theorem 3.8) is the fact that a similar result holds for the labeled disjoint union.

Corollary 3.10 If Conjecture 3.9 holds for two labeled posets (P_{1}, ω_{1}) and (P_{2}, ω_{2}) then it also holds for (P_{1} ⊎ P_{2}, ω_{1} ⊎ ω_{2}).

Despite its deceiving simplicity, Corollary 3.10 is highly non-trivial and we refer the reader to [57], Theorem 0.2, for its proof (see also [4], p. 5, and [58], Corollary 14). In particular, since ω_{1} ⊎ ω_{2} is natural if ω_{1} and ω_{2} are natural, Corollary 3.10 reduces Conjecture 1 of [51] to connected posets.

While there are several equivalent ways of stating Conjecture 3.9 (see [4], Chapter 1, and [51], p. 506, for natural labelings) one new necessary and sufficient condition for it to hold has been obtained. Since this uses the theory of total positivity, we will treat it in section 8.

We conclude our discussion of Conjecture 3.9 by mentioning that a Coxeter group generalization of it has been proposed in [38] using the concept of parset (which is a Coxeter group analogue of the concept of labeled poset, a labeled poset being equivalent to a parset of type A_{n}, see [39], p. 33).

V. Reiner notes in [38] that the analogue of Conjecture 3.9 is false in this more general context, but conjectures that it is true whenever the Dynkin diagram of the Coxeter system has no forks (see [38]). No work has been done on this more general conjecture so far, and the conjecture itself is at present unpublished.

A new sufficient condition for Conjecture 3(a) of [51] (i.e., that the chromatic polynomial of a graph is log-concave) has been obtained in [6] (see Theorem 6.2), using the theory of total positivity, and is discussed in Section 8. Conjecture 3(a) is currently known to be true for triangulated graphs, outerplanar graphs, wheels and broken wheels, generalized theta graphs, hyperoctahedral graphs, complete bipartite graphs, and several classes of line graphs (see [18], and [6]). While not much direct progress has been made on Conjecture 3(a) several related conjectures have appeared and have been studied in the literature since the appearance of [51]. Let χ(G; x) be the chromatic polynomial of a graph G on p vertices and write

χ(G; x) = ∑_{i=0}^{p} a_{i}(x)_{i} = ∑_{i=0}^{p}(−1)^{p−i}c_{i}⟨x⟩_{i}.

Then we conjecture the following.

Conjecture 3.11 For any graph G the polynomial ∑_{i=0}^{p} a_{i}x^{i} is log-concave.

The following conjecture appears in [59], Conjecture 1.9 (see also [6], Problem 7.1, and [8], Question 6.9).

Conjecture 3.12 For any graph G the polynomial ∑_{i=0}^{p} c_{i}x^{i} has only real zeros.

Both conjectures are open even for the unimodality statement. Conjecture 3.11 is known to be true for cocomparability graphs, complements of trianglefree graphs, complete multipartite graphs, trees, board graphs, supersolvable graphs, and cycles (see [6], §3, and [8], §4, for definitions and proofs of these results).

Conjecture 3.12 is known to be true for supersolvable graphs and cycles (see [6], Theorem 6.1, and [8], Proposition 5.8). Also, it is known that it is enough to prove Conjecture 3.12 for connected graphs (see [8], Proposition 5.12). Both conjectures have been verified for graphs on at most 9 vertices.

Finally, we mention the following conjecture which appears in [6], Conjecture 7.5.

Conjecture 3.13 Let G be a graph. Then the sequence {χ(G; n)}_{n∈N} is log-concave.

Note that the sequence {χ(G; n)}_{n∈N} is not in general P F (take, e.g., the ladder on 6 vertices). Conjecture 3.13 is known to be true for all the graphs for which Conjecture 3.11 is currently known to be true, even though it is not a special case of Conjecture 3.11. There is a relationship between Conjectures 3.11 and 3.13 which can be proved using the theory of total positivity, and which will be explained in section 8.

4 Analytic Techniques

Some new unimodality results have been obtained since the appearance of [51] using the analytic techniques described in section 4 of [51]. In particular, B. Richmond and A. Knopfmacher have used these techniques to prove the following result (see [40], Theorem 1). Theorem 4.1 For n ∈ P and k ∈ [n] let C(n, k) be the number of compositions of n into k distinct parts. Then the polynomial ∑_{k≥0} C(n, k)x^{k} is unimodal.

This result complements (and completes) similar results (all mentioned in [51], §4, p. 509) that have been obtained for the number of compositions of n into k parts and for the number of partitions of n into k parts, and into k distinct parts.

The conjecture mentioned in [51], §4, p. 510, namely that the polynomial

∏_{k=1}^{n} \frac{(1 − q^{rk})}{(1 − q^{k})} (3)

is unimodal for r even and n ∈ P, and for r odd and n ≥ 11 is still open and no new results have been obtained on it. The conjecture is currently known to be true for 2 ≤ r ≤ 20 and for r = 100, 101 ([2]). It is interesting to note that this conjecture can be rephrased entirely in terms of principal specializations of symmetric functions. Let δ be the staircase partition of length n (i.e., δ = (n, n − 1, …, 3, 2, 1)). Then the conjecture merely asserts that

p_{δ}(1, q, q^{2}, …, q^{r−1})

is a unimodal polynomial if n and r satisfy the above conditions (here p_{λ} denotes a power sum symmetric function). While it is easily seen that p_{λ}(1, q, …, q^{r−1}) is not in general a unimodal polynomial, it is well known that s_{λ}(1, q, …, q^{r−1}) always is (see, e.g., [29], Chapter I, §8, Exercise 4). So it is possible that a more refined knowledge of the connection coefficients between these two bases of the ring of symmetric functions (i.e., of the character table of the symmetric group, see, e.g., [29], Chapter I, §7) or some plethysm argument (as used, e.g., in [29], Chapter I, §8, Exercise 4) may yield a proof of the conjecture.

5 Mixed Volumes

No new combinatorial applications of the mixed volumes technique (i.e., of the Aleksandrov-Fenchel inequalities) seem to have appeared in the literature since the publishing of [51]. However, some work has been done on Conjecture 4(a) of §5 of [51] (i.e. that the h-vector of a standard graded Cohen-Macaulay domain is log-concave). This conjecture has been disproved by Niesi and Robbiano in [32], Examples 2.3 and 2.4 (see also [41]), though they were unaware of Stanley’s conjecture and their motivation came from a conjecture of Hibi (which their example also disproves). Other inequalities for the h-vector of a standard graded Cohen-Macaulay domain (though not directly related to unimodality) have been established in [52] and [21].

There are several natural weakenings of Conjecture 4(a) of [51] which are still open. Probably the most plausible one is the following, which is due to Hibi (see [21], Conjecture 1.5). We follow the terminology of [47]. Conjecture 5.1 Let R be a graded standard Gorenstein domain and let (h_{0}, h_{1}, …, h_{s}) be its h-vector (i.e.,

∑_{i≥0} H(R, i)x^{i} = \frac{h_{0} + h_{1}x + … + h_{s}x^{s}}{(1 − x)^{d}}

in Z[[x]], where {H(R, i)}_{i∈N} is the Hilbert function of R and d is the Krull dimension of R). Then the sequence (h_{0}, h_{1}, …, h_{s}) is unimodal.

Note that the statement of the conjecture is open also if we substitute the word “Gorenstein” with “Cohen-Macaulay” or if we substitute the word “unimodal” with “log-concave”. Also note that it follows from a well known result of Stanley ([47], Theorem 4.4) that the sequence (h_{0}, …, h_{s}) is symmetric in the hypothesis of the conjecture. Conjecture 5.1 has been proved for rings of codimension ≤ 3 by Valla in [55], and for rings with s ≤ 5 by Stanley in [52].

The h-vectors of several classes of Gorenstein domains arising from “generalized determinantal varieties” have recently been given combinatorial interpretations in terms of non-intersecting paths in certain directed graphs by Conca and Kulkarni (see [15] and [25]). It is possible that these combinatorial interpretations may yield counterexamples to (or evidence for) Conjecture 5.1.

We note another weakening of Conjecture 4(a) of [51] which has not been considered before in the literature, but which we believe to be true.

Conjecture 5.2 Let R be a standard graded Gorenstein domain. Then the sequence {H(R, i)}_{i∈N} is log-concave.

The fact that this conjecture is a special case of Conjecture 4(a) of [51] follows from the theory of total positivity, and will be explained in section 8.

Conjecture 4(b) of [51] is still open (even in the most general of the formulations given in [51]), and no work seems to have been done on it. We only mention that the conjecture is open even in the case of complex determinantal varieties (i.e., when A = C[x_{1,1}, …, x_{m,n}] and I is the homogeneous ideal generated by all the r × r minors of the matrix (x_{i,j})_{1≤i≤m,1≤j≤n}, in the notation of [51]). In this case, Lascoux’s resolution (see [26]) yields a combinatorial formula for the Betti numbers of A/I as an A-module, but it’s difficult to see whether this implies their log-concavity.

6 Linear Algebra and Finite Groups

Conjecture 5 of [51] is still open and no partial results have been obtained on it. Recall that the conjecture asserts that the sequence (j_{0}(r_{1} × … × r_{m}), …, j_{r}(r_{1} × … × r_{m})) is unimodal for any r_{1}, …, r_{m} ∈ P, where r = r_{1} … r_{m}, and where j_{k}(r_{1} × … × r_{m}) equals the number of order ideals of size k of the poset r_{1} × … × r_{m} (the direct product of m chains of sizes r_{1}, …, r_{m}). As already noted in [51], this conjecture is known to be true if m ≤ 3. Note that if r_{1} = … = r_{m} = 2 then the conjecture simply asserts that the number of (abstract) simplicial complexes on n vertices having k simplices is a unimodal function of k as k = 0, …, 2^{n}.

Since for m = 2 the conjecture is equivalent to the statement that the number of partitions of size k fitting into an r_{1} × r_{2} rectangle is a unimodal function of k it is natural to look for analogous sequences arising from partitions which are not rectangles. More precisely, let λ = (λ_{1}, …, λ_{r}) be a partition and let j_{k}(λ) be the number of partitions μ of size k whose Ferrers diagram is contained in that of λ (i.e., those μ = (μ_{1}, …, μ_{r}) such that ∑_{i=0}^{r} μ_{i} = k, and μ_{i} ≤ λ_{i} for i = 1, …, r), for k = 0, …, |λ|. The unimodality of the sequence (j_{0}(λ), …, j_{|λ|}(λ)) has been investigated by D. Stanton in [53]. While the sequence is not unimodal in general (the “smallest” example is λ = (8, 8, 4, 4)), Stanton proves in [53] (see Theorem 7) that it is if λ has at most three parts. Also, he conjectures ([53], Conjecture 1) that the following holds. Conjecture 6.1 Let λ = (λ_{1}, …, λ_{r}) be a self-conjugate partition. Then the sequence (j_{0}(λ), …, j_{|λ|}(λ)) is unimodal.

The above conjecture has been verified for |λ| ≤ 124, and is known to be true if λ_{3} ≤ 2 ([53], Theorem 11). We should mention that Conjecture 6.1 is open even for staircases (see [53], Conjecture 2).

7 The Hard Lefschetz Theorem

Despite the generality of the techniques and results described in §§7 and 8 of [51] not many new applications of them to combinatorics have been found. One of them (which seems to have been overlooked in [51]) was noted in [9] (see Theorem 2.4), and is a (partial) “dual” result to Theorem 19 of [51]. We follow [22] for terminology, notation, and definitions regarding Coxeter groups. In particular, for a Coxeter system (W, S) and x ∈ W we

let d(x) =^{def} |{s ∈ S : l(xs) < l(x)}|.

Theorem 7.1 Let (W, S) be a finite Coxeter system. Then the polynomial

∑_{x∈W} q^{d(x)} (4)

is symmetric and unimodal.

The preceding result follows from Theorem 20 of [51] and known facts on Coxeter complexes (see [9], §2, for details). In this respect, we should mention the following conjecture which appears in [9] (see Conjecture 5.2).

Conjecture 7.2 Let (W, S) be a finite Coxeter system. Then the polynomial in (4) has only real zeros.

It is proved in [9] that this conjecture holds for all finite irreducible Coxeter systems of type different from D. Also, it is easy to see that it is enough to prove Conjecture 7.2 for irreducible Coxeter systems. It has been verified that the polynomial in (4) has only real zeros if (W, S) is of type D_{n} with n ≤ 23.

Conjecture 6 of [51] is still open even in its most general statement. Theorem 22 of [51] has been considerably generalized by Adin in [1].

Let Q be a d-polytope. A linear symmetry of Q is an invertible linear transformation of R^{d} which maps Q into itself. Given p ∈ P, we say that Q is p-symmetric if Q has a linear symmetry L such that:

i) L(x) ≠ x for all x ∈ R^{d} \ {0};

ii) L has order p as an element of the symmetry group of Q.

It is not hard to see that if Q is p-symmetric then p − 1 divides d.

Theorem 7.3 Let p be a prime and Q be a p-symmetric rational simplicial d-polytope, with h-vector (h_{0}, h_{1}, …, h_{d}). Then the polynomial

∑_{i=0}^{d} h_{i}q^{i} − (1 + q + … + q^{p−1})^{\frac{d}{p−1}}

is unimodal (and symmetric).

Note that Q is 2-symmetric if and only if it is centrally symmetric in the sense of [51], p. 528. The above theorem reduces to Theorem 22 of [51] if p = 2. The techniques used in the proof of Theorem 7.3 are refinements of those used by Stanley to prove Theorem 22 of [51] (see [1], for the details).

As briefly mentioned in [51], p. 529, Propositions 12 and 13 are both special cases of a much more general result. Let P be the set of all (integer) partitions. We say that a basis {a_{λ}}_{λ∈P} of Λ_{Q} ( =^{def} Λ ⊗_{Z} Q) is standard if {a_{λ} : |λ| = n} is a basis of (Λ_{Q})_{n} for all n ∈ N. We say that an ordered triple ({a_{λ}}_{λ∈P} , {b_{λ}}_{λ∈P} , {c_{λ}}_{λ∈P}) of standard bases of Λ_{Q} is compatible if:

(i) if c_{λ} = ∑_{μ} f_{λ μ} a_{μ} then f_{λ μ} ≥ 0, for all λ , μ ∈ P;

(ii) if a_{λ} b_{μ} = ∑_{ν} g_{λ μ}^{ν} a_{ν} then g_{λ μ}^{ν} ≥ 0, for all λ , μ , ν ∈ P.

For brevity, we call a symmetric unimodal polynomial p with nonnegative coefficients a Λ-polynomial and we denote by C(p) its center of symmetry.

Theorem 7.4 Let {r_{μ}(q)}_{μ∈S} , {u_{ν}(q)}_{ν∈T} be two families of Λ-polynomials, where S, T ⊆ P and (0) ∉ S. Suppose that there exists n, k ∈ Z such that

C(r_{μ}) = \frac{n |μ|}{2} , C(u_{ν}) = \frac{n |ν| + k}{2} ,

for all μ ∈ S, ν ∈ T. For ρ ∈ P, define a polynomial R_{ρ}(q) by

∑_{ρ∈P} R_{ρ}(q)a_{ρ} = \frac{∑_{ν∈T}u_{ν}(q)c_{ν}}{1 − ∑_{μ∈S}r_{μ}(q)b_{μ}} , (5)

where ({a_{λ}}_{λ∈P} , {b_{λ}}_{λ∈P} , {c_{λ}}_{λ∈P}) is a compatible triple of standard bases of Λ_{Q}. Then R_{ρ}(q) is a Λ-polynomial and C(R_{ρ}) = \frac{n|ρ|+k}{2}.

The above theorem is proved inductively and we refer the reader to [5], Theorem 2, for its proof. As such, we could have placed Theorem 7.4 in §2, but we have decided to put it here since it generalizes Propositions 12 and 13 of [51].

Although not many new applications of the Hard Lefschetz Theorem to combinatorics have been obtained since the publication of [51], we should point out that one major application of it (namely Theorem 20 of [51]) now has a proof that avoids the Hard Lefschetz Theorem. Finding such a proof has been a challenge to several mathematicians (see, e.g., [11], p. 149, and [33], p. 266) ever since Stanley’s original proof appeared ([48], see also [49]). The new proof has been found by McMullen as part of his new proof of the characterization of the h-vector of a simplicial d-polytope (see [31]) and uses the concept and machinery of the polytope algebra (see [30]). This is the most elementary proof of Theorem 20 of [51] known to date.

Concerning Proposition 14 of [51] we should point out that this is just a special case of Conjecture 3.9. In fact, if P_{λ} is a Ferrers poset of shape λ and ω is a column strict labeling of it (see [4], §5.2, for definitions) then W ((P_{λ}, ω); q) = qT_{λ}(q) (where T_{λ}(q) has the same meaning as in Proposition 14 of [51]). This fact, which was known to Stanley but not explained in [51] (see p. 530), is proved in [4], §5.3.

8 Total Positivity

As mentioned at the end of §2 many results similar to those at the end of §2 of [51] have been obtained since its appearance. These results have all been proved with techniques from the theory of total positivity (see [23]) and have later been applied to log-concavity and unimodality problems.

The key observation leading to these results is that the operation on sequences considered by Stanley at the end of §2 of [51] (see Propositions 1,2, and 3), is bilinear (namely, convolution). Thus one may ask for other “naturally arising” linear transformations on polynomials that preserve the log-concavity and/or unimodality property. As noted in [50], §4.3, p. 208, there are several bases of the space V_{d} of (real) polynomials of degree ≤ d that are used often in combinatorics. In particular, Stanley in [50] mentions

four, namely: \{x^{i}\}_{i=0,...,d}; \{(\begin{matrix}x \\ i \end{matrix})\}_{i=0,...,d}; \begin{cases}( \\ ( & \begin{matrix}x \\ i \end{matrix} & ) \\ & ) \end{cases}\}_{i=0,...,d} (where \begin{aligned}( \\ ( & \begin{matrix}x \\ i \end{matrix} & ) \\ & ) \end{aligned} =^{def}

(−1)^{i} (\begin{matrix}−x \\ i \end{matrix}) ); and \{(\begin{matrix}x+d−i \\ d \end{matrix})\}_{i=0,...,d}. It is therefore natural to look for the linear transformations that send one of these bases to another. In other words, one may ask, for example, whether if ∑_{i=0}^{d} c_{i} (\begin{matrix}x \\ i \end{matrix}) = ∑_{i=0}^{d} a_{i} \begin{aligned}( \\ ( & \begin{matrix}x \\ i \end{matrix} & ) \\ & ) \end{aligned} and {a_{0}, …, a_{d}} is log-concave then {c_{0}, …, c_{d}} is also log-concave. The answer to these kind of questions is easily seen to be almost always no unless one adds the condition (already present also in Propositions 2 and 3 of [51]) that the sequences have no internal zeros. In this case, however, many such questions have affirmative answers. In order to state the results in a reasonably compact way it is convenient to introduce the following notation. Given a basis {v_{0}(x), …, v_{d}(x)} of V_{d} we let P F_{2}[v_{i}(x)] be the set of polynomials of V_{d} whose coefficients, with respect to the basis {v_{0}(x), …, v_{d}(x)}, form a nonnegative log-concave sequence with no internal zeros, (the notation P F_{2} actually has a precise motivation, see [4], Proposition 2.5.1). Theorem 8.1 Let d ∈ P. Then the following strict inclusions hold:

P F_{2} [\begin{matrix}( \\ ( & \begin{matrix}x \\ i \end{matrix} & ) \\ & ) \end{matrix}] ⊂ P F_{2}[⟨x⟩_{i}] ∩ P F_{2} [(\begin{matrix}x \\ i \end{matrix})] ,

P F_{2} [(\begin{matrix}x+d−i \\ d \end{matrix})] ⊂ P F_{2} [(\begin{matrix}x \\ i \end{matrix})] ⊂ P F_{2}[(x)_{i}].

The preceding theorem can be proved by using results from the theory of total positivity and we refer the reader to [4], §2.2, for its proof. (Note that the inclusion P F_{2} [\begin{matrix}( \\ ( & \begin{matrix}x \\ i \end{matrix} & ) \\ & ) \end{matrix}] ⊂ P F_{2} [(\begin{matrix}x \\ i \end{matrix})] answers in the affirmative the sample question posed in the preceding paragraph.) One can check (see also the Appendix on p. 103 of [4]) that the transitive closure of the inclusions in Theorem 8.1 give all possible inclusions with possibly the following exception.

Problem 8.2 Is it true that P F_{2} [\begin{matrix}( \\ ( & \begin{matrix}x \\ i \end{matrix} & ) \\ & ) \end{matrix}] ⊆ P F_{2}[x^{i}]?

This problem first appeared in [4], p. 26, and is still open.

There are, of course, many equivalent ways of stating the various inclusions in Theorem 8.1, some of which may be more intuitive (though less compact). For example, the inclusion P F_{2} [(\begin{matrix}x+d−i \\ d \end{matrix})] ⊂ P F_{2} [(\begin{matrix}x \\ i \end{matrix})] can be shown to be equivalent to the following result.

Corollary 8.3 Let {a_{0}, …, a_{d}} be a nonnegative log-concave sequence with no internal zeros. Then the sequence

\{∑_{i=0}^{d} (\begin{matrix}i \\ j \end{matrix} ) a_{i}\}_{j∈N}

is log-concave.

This, in turn, can be restated in an even more concrete form.

Corollary 8.4 Let P (x) ∈ R[x] be log-concave, with nonnegative coefficients and no internal zeros. Then P (1 + x) is log-concave.

All the other inclusions in Theorem 8.1 can be restated in similar equivalent ways, however, for reasons of space we have decided to present them in “set inclusion” form.

A simple application of Corollary 8.3 to combinatorics is the following new sufficient condition for Conjecture 3 (a) of [51] to hold. (We refer the reader to, e.g., [3], p. 88, for the definition of the internal and external activities of a spanning tree.)

Theorem 8.5 Let G be a connected graph on p vertices and let, for i = 1, …, p − 1, t_{i} be the number of spanning trees of G having internal activity i and external activity 0. Suppose that the sequence {t_{1}, …, t_{p−1}} is logconcave with no internal zeros, then (−1)^{p}χ(G; −x) is log-concave.

The preceding result appears in [6] (see Theorem 6.2), and its proof is an almost straightforward application of Corollary 8.3.

In view of Theorem 2.3 and Conjecture 3.13 one may also ask for conditions on a polynomial A(x) ∈ R[x] that imply that the sequence {A(n)}_{n∈N} is log-concave. It turns out that polynomials in P F_{2} [(\begin{matrix}x \\ i \end{matrix})] and P F_{2} [(\begin{matrix}x+d−i \\ d \end{matrix})] do have this property.

Theorem 8.6 Let A(x) = ∑_{i=0}^{d} a_{i} (\begin{matrix}x \\ i \end{matrix}), and B(x) = ∑_{i=0}^{d} a_{i} (\begin{matrix}x+d−i \\ d \end{matrix}) ∈ R[x],

and suppose that {a_{0}, …, a_{d}} is a nonnegative log-concave sequence with no internal zeros. Then the sequences {A(n)}_{n∈N} and {B(n)}_{n∈N} are logconcave.

The statement for A(x) is proved in [4], Theorem 2.5.7 (see also [23], Theorem 7.3, p.142) using the theory of total positivity. The second one follows from the first one by Theorem 8.1. Note that Theorem 8.6 gives a relationship between Conjectures 3.11 and 3.13. Namely, if χ(G; x) = ∑_{i=0}^{d} a_{i}(x)_{i} and ∑_{i=0}^{d} i!a_{i}x^{i} is log-concave (a statement slightly stronger than Conjecture 3.11) then Conjecture 3.13 holds.

Again, it is possible to restate the preceding result in many equivalent ways. For example, using the binomial theorem (see, e.g., [50], p. 16) we obtain the following.

Corollary 8.7 Let B(x) ∈ R[x], and w(x) be the B-Eulerian polynomial. Then, if w(x) has nonnegative log-concave coefficients with no internal zeros, the sequence {B(n)}_{n∈N} is log-concave.

The preceding result, in turn, can actually be generalized as follows, (see [4], Theorem 2.2.2, for the proof of an even more general statement).

Theorem 8.8 Let d ∈ N, w(x) ∈ R[x] have nonnegative log-concave coefficients with no internal zeros, and let

∑_{i≥0} a_{i}x^{i} =^{def} \frac{w(x)}{(1 − x)^{d}}

in R[[x]]. Then the sequence {a_{i}}_{i∈N} is log-concave.

Note that since W ((P, ω); x) is the Ω((P, ω); x)-Eulerian polynomial (see, [46], Proposition 8.3, p. 24) the preceding result implies that Theorem 2.3 is a special case of Conjecture 3.9 as well as that Conjecture 5.2 is a weakening of Conjecture 4 (a) of [51].

Finally, we mention the following result.

Theorem 8.9 Let f(x) ∈ R[x] and w(x) be the f-Eulerian polynomial. Then the following are equivalent:

i) w(x) has nonnegative coefficients and only real zeros;

ii) the sequence {f(n)}_{n∈N} is P F.

The preceding theorem is the deepest of the results presented in this section, and its proof follows from the characterization theorem of P F sequences (see, [23], Theorem 5.3, p. 412, and also [4], Theorem 4.5.2) which in turn uses deep results from the Nevanlinna theory of meromorphic functions and is one of the cornerstones (and greatest achievements) of the theory of total positivity. We refer the reader to [4], Theorem 4.6.2, for its proof.

In view of the relationship between W ((P, ω); x) and Ω((P, ω); x) mentioned above the preceding result immediately implies the following necessary and sufficient condition for Conjecture 3.9 to hold.

Theorem 8.10 Let (P, ω) be a labeled poset. Then the following are equivalent:

i) W ((P, ω); x) has only real zeros;

ii) the sequence {Ω((P, ω); s)}_{s∈N} is P F.

Since the combinatorial meaning of Ω((P, ω); s) is simpler than that of the coefficients of W ((P, ω); x) (for example, we don’t know whether W ((P, ω); x) is log-concave, but we know that {Ω((P, ω); s)}_{s∈N} is), it is quite conceivable that a solution of Conjecture 3.9 will use the preceding theorem.

It is natural to ask whether any of the results in this section have analogues for unimodal polynomials. As noted in [4], p. 26, this is false. Unimodality alone seems to be too much of a weak property, and almost any reasonable transformation will destroy it. This may be one of the reasons why unimodality can be so difficult to establish. Similar considerations apply to symmetric unimodal polynomials.

References

[1] R. Adin, On face numbers of rational simplicial polytopes with symmetry, preprint.

[2] G. Almkvist, Proof of a conjecture about unimodal polynomials, J. Number Theory, 32 (1989), 43-57.

[3] N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974.

22 FRANCESCO BRENTI

[4] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no.413, 1989.

[5] F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc., 108 (1990), 1133-1141.

[6] F. Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc., 332(1992), 729-756.

[7] F. Brenti, Determinants of super-Schur functions, lattice paths, and dotted plane partitions, Adv. in Math., 98(1993), 27-64.

[8] F. Brenti, G. Royle, and D. Wagner, Location of zeros of chromatic and related polynomials of graphs, Canadian J. Math., to appear.

[9] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, Europ. J. Combinatorics, to appear.

[10] F. Brenti, Combinatorics and total positivity, J. Combin. Theory Ser. A, to appear.

[11] A. Brøndsted, An Introduction to Convex Polytopes, Graduate Texts in Mathematics 90, Springer-Verlag, New York, 1983.

[12] L. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc., 101(1987),771-775.

[13] L. Butler, The q-log concavity of q-binomial coefficients, J. Combin. Theory Ser. A, 54 (1990), 54-63.

[14] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

[15] A. Conca, Symmetric ladders, preprint.

[16] D. Daykin, J. Daykin, and M. Paterson, On log-concavity for order preserving maps of partial orders, Discrete Math., 50 (1984), 221-226.

[17] A. Edrei, Proof of a conjecture of Schoenberg on the generating function of a totally positive sequence, Canadian J. Math., 5 (1953), 86-94.

[18] D. Gernert, A survey of partial proofs for Read’s conjecture and some recent results, IX symposium on operations research. Part I. Sections 1-4 (Osnabruck, 1984), 233-238, Methods Oper. Res., 49, Athenaum/Hain/Hanstein, Konigstein/Ts., 1985.

[19] F. Goodman, K. O’Hara, and D. Stanton A unimodality identity for a Schur function specialization, J. Combin. Theory Ser. A, 60 (1992), 143-146.

[20] I. Goulden and D. Jackson, Combinatorial Enumeration, John Wiley, New York, 1983.

[21] T. Hibi, Flawless O-sequences and Hilbert functions of Cohen-Macaulay integral domains, J. Pure Appl. Alg., 60 (1989), 245-251.

[22] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

[23] S. Karlin, Total Positivity, vol.1, Stanford University Press, 1968.

[24] C. Krattenthaler, On the q-log-concavity of Gaussian binomial coefficients, Monatsh. Math., 107 (1989), 333-339.

[25] D. Kulkarni, Hilbert polynomial of a certain ladder-determinantal ideal, J. Algebraic Comb., 2 (1993), 57-71.

[26] A. Lascoux, Syzygies des variétés déterminantales, Adv. in Math., 30 (1978), 202-237.

[27] P. Leroux, Reduced matrices and q-log concavity properties of q-Stirling numbers, J. Combin. Theory Ser. A, 54 (1990), 64-84.

[28] B. J. Levine, Distribution of Zeros of Entire Functions, Amer. Math. Soc., Translations of Math. Monographs, 5, Providence, 1964.

[29] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

[30] P. McMullen The polytope algebra, Adv. in Math., 78 (1989), 76-130.

[31] P. McMullen On simple polytopes, Invent. Math., 113 (1993), 419-444.

[32] G. Niesi and L. Robbiano Disproving Hibi’s conjecture with CoCoA or Projective curves with bad Hilbert functions, Proceedings of MEGA 92, to appear.

[33] T. Oda, Simple convex polytopes and the strong Lefschetz theorem, J. Pure Appl. Alg., 71 (1991), 265-286.

[34] K. O’Hara, Unimodality of Gaussian coefficients: a constructive proof, J. Combin. Theory Ser. A. 53 (1990) 29-52.

[35] G. Pólya and G. Szegö, Problems and Theorems in Analysis, vols. I and II, Springer-Verlag, Berlin, Heidelberg, 1976.

[36] F. Regonati Sui numeri di sottogruppi di dato ordine nei p-gruppi abeliani finiti, Istit. Lombardo Rend. Sci. A, 122 (1988), 369-380.

[37] F. Regonati Whitney numbers of the second kind of finite modular lattices, J. Combin. Theory Ser. A, 60 (1992), 34-49.

[38] V. Reiner, Quotients of Coxeter complexes and P-Partitions, Ph.D. Thesis, 1990, Massachusetts Institute of Technology.

[39] V. Reiner, Quotients of Coxeter complexes and P-Partitions, Memoirs Amer. Math. Soc., no.460, 1992.

[40] B. Richmond and A. Knopfmacher, Compositions with distinct parts, preprint, June 1993.

[41] L. Roberts, Certain projective curves with bad Hilbert function or Disproving the Hibi conjecture without CoCoA, Math. preprint no. 1993-05, Queen’s Univ., Ontario, Canada, June 1993.

[42] B. Sagan, Inductive and injective proofs of log concavity results, Discrete Math., 68 (1988), 281-292.

[43] B. Sagan, Inductive proofs of q-log concavity, Discrete Math., 99 (1992), 289-306.

[44] B. Sagan, Log-concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinant, Trans. Amer. Math. Soc., 329 (1992), 795-812.

[45] I. Schur, Zwei Sätze über algebraische gleidhungen mit laiter reellen wurzeln, J. reine angew. Math. 144 (1914), 75-88.

[46] R. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc., no.119, 1972.

[47] R. Stanley, Hilbert functions of graded algebras, Adv. in Math., 28 (1978), 57-83.

[48] R. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math., 35 (1980), 236-238.

[49] R. Stanley, The number of faces of simplicial polytopes and spheres, Annals of the New York Academy of Sciences, 440 (1985), 212-223.

[50] R. Stanley, Enumerative Combinatorics, vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[51] R. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences, 576 (1989), 500-534.

[52] R. Stanley, On the Hilbert function of a graded Cohen-Macaulay domain, J. Pure Appl. Alg., 73 (1991), 307-314.

[53] D. Stanton Unimodality and Young’s lattice, J. Combin. Theory Ser. A, 54 (1990), 41-53.

[54] J. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math., 99 (1992), 307-320.

[55] G. Valla, The h-vector of a Gorenstein codimension three graded domain, preprint.

[56] M. Wachs and D. White, p,q-Stirling numbers and set partition statistics, J. Combin. Theory Ser. A, 56 (1991), 27-46.

[57] D. Wagner, Total positivity of Hadamard products, J Math. Analysis and Applications, 163 (1992), 459-483.

[58] D. Wagner, Enumeration of functions from posets to chains, Europ. J. Combinatorics, 13 (1992), 313-324.

[59] D. Wagner, Zeros of rank-generating functions of Cohen-Macaulay complexes, Proceedings of Fourth Formal Power Series and Algebraic Combinatorics Conference, Montreal, 1992, Discrete Math., to appear.

[60] D. Zeilberger, Kathy O’ Hara’ s Constructive Proof of the Unimodality of the Gaussian Polynomials, Amer. Math. Monthly, 96 (1989), 590-