The Applications of Total Positivity to Combinatorics, and conversely

Francesco Brenti^{1}

1 Introduction

Total positivity is an important and powerful concept that arises often in various branches of mathematics, statistics, probability, mechanics, economics, and computer science ( see, e.g., [24], and the references cited there). In this paper we give a survey of the interactions between total positivity and combinatorics.

The historical origins of these connections date from the mid 1980’s when it was observed that many total positivity techniques and results had applications to unimodality problems arising in combinatorics. Many different fields of mathematics had been previously applied to unimodality problems, but not total positivity. This approach proved to be extremely successful and many unimodality problems that had resisted attack by other techniques were solved in this way. In turn, the combinatorial problems themselves suggested the study of questions in total positivity that had never been studied before. One of these is the study of linear and bilinear transformations that preserve the P F or T P property of a sequence or matrix, respectively. Some combinatorialists initiated a study of these questions and then applied their results to the combinatorial problems which originally motivated them. We survey these results in §3 and several outstanding open problems in §6 which show that the theory of linear and bilinear transformations which preserve the P F or T P properties, though rich with non-trivial results, has yet to reach its full maturity.

Up to this point the applications of total positivity to combinatorics had been mainly applications of the theory of P F sequences. At the end of the 1980’s it was slowly realized that, in fact, not only P F sequences but also T P matrices are quite ubiquitous in combinatorics. While most of the familiar combinatorial matrices (such as, for example, the binomial and Stirling matrices) could be easily proved to be T P as an application of the general theory of total positivity, it also became apparent that for many of them it is in fact possible to give a combinatorial interpretation of their minors, thus showing, in particular, that they are nonnegative. These were the first examples of combinatorial proofs of total positivity, though the basic ideas used in them were already present in works of Karlin-McGregor, Lindström and Gessel-Viennot. Continuing this train of thought leads to a completely combinatorial characterization of totally positive matrices, which automatically affords a combinatorial interpretation of all their minors. This result, and several variants of it, are extremely powerful tools for proving that an impressive variety of matrices arising in combinatorics (such as various matrices of (p, q)-Stirling numbers of both kinds, q-Lah numbers, etc...) are indeed T P. For many of these results the combinatorial proof is the only one known to date. The combinatorial approach is also useful from a theoretical point of view. For example, the well known property that T P matrices are closed under products is obvious from the combinatorial standpoint, and more difficult results (such as, e.g., that immanants of T P matrices are nonnegative) have simpler proofs in this setting. We survey these results in §4. Despite the power of the combinatorial approach, however, many matrices arising from combinatorics are still only conjectured to be T P, and we survey the main conjectures in this area in §6.

1Partially supported by NSF grant DMS 9304580 and by EC grant No. CHRX-CT93-0400.

Recently there has been much interest in combinatorics in extending what is known for the symmetric group to other finite Coxeter groups. In particular, concepts that generalize total positivity have been introduced and studied for any Coxeter group. These concepts coincide with usual total positivity in the case of the symmetric group. These studies are still in their infancy, and we survey them in §5 and point out some promising directions for further research in §6. Given the wide applicability that total positivity has it is very reasonable to expect that these natural generalizations will prove equally useful.

2 Notation and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of the paper. We let P =^{def} {1, 2, 3, …}, N =^{def} P ∪ {0}, Q be the set of rational numbers, R be the set of real numbers and R^{+} =^{def} {x ∈ R : x ≥ 0}; for a ∈ N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|, for r ∈ N we let (\begin{matrix}A \\ r \end{matrix}) =^{def} \{T ⊆ A : |T | = r\}. Given a polynomial P (x), and i ∈ Z, we denote by [x^{i}](P (x)) the coefficient of x^{i} in P (x).

We follow [41] for general combinatorial notation and terminology. In particular, given a (finite) set T we denote by Π(T) the set of all (set) partitions of T (see, e.g., [41], p.33 for further information about partitions of a set), and by S(T) the set of all bijections from T to itself. For n ∈ P, we let S_{n} =^{def} S([n]). Throughout this work, p, q, and x will denote independent variables. For n ∈ P we let [n]_{p,q} =^{def}

p^{n−1} + q p^{n−2} + q^{2}p^{n−3} + … + q^{n−1}, [n]_{q} =^{def} [n]_{1,q}, and [k]_{p,q} =^{def} 0 if k ≤ 0.

Given a commutative ring F (usually Z, Q, or R) we denote by F [[x]] the ring of formal power series in the one variable x with coefficients in F. We refer the reader to [41], §1.1, pp. 3-8, for the fundamental properties of F [[x]] which we will use.

We follow [30], §I.1, for notation and terminology related to partitions of integers. Recall that given n ∈ P a partition of n is a sequence λ =^{def} (λ_{1}, …, λ_{r}) (for some r ∈ P) of positive integers such that λ_{1} ≥ … ≥ λ_{r} > 0 and ∑_{i=1}^{r} λ_{i} = n. We call r the length of λ and write r = l(λ).

An infinite (real) matrix M = (M_{n,k})_{n,k∈N} (where M_{n,k} is the entry in the n-th row and k-th column of M) is said to be totally positive (or, T P, for short) if every minor of M has nonnegative determinant. An infinite (real) sequence {a_{i}}_{i∈N} is said to be a Pólya frequency sequence (or, a P F -sequence, for short) if the infinite matrix A =^{def} (a_{n−k})_{n,k∈N} (where a_{i} =^{def} 0 if i < 0) is totally positive. Given a matrix M we denote by M′ the transpose of M. We will often work with matrices and sequences whose elements are real polynomials over some (possibly infinite) set of independent variables x. In this case we say that such a matrix M = (M_{n,k})_{n,k∈N} is x-T P if the determinant of any minor of M is a polynomial with nonnegative coefficients and we define x−P F in the natural way. Given a sequence of independent variables {x_{i}}_{i∈N} and T ⊆ N we let x_{T} =^{def} ∏_{i∈T} x_{i}. We also let 0 =^{def} (0, 0, 0, …) and 1 =^{def} (1, 1, 1, …).

3 Total Positivity and Unimodality

As noted in the Introduction, the interactions between total positivity and combinatorics have their origin in the observation that total positivity results and techniques can be effectively used in the solution of unimodality problems. In this section we describe some of these problems and their solution using total positivity, as well as total positivity results that have been motivated by unimodality problems.

A sequence of real numbers {a_{i}}_{i=0,...,d} is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{0} ≤ a_{1} ≤ … ≤ a_{j} ≥ a_{j+1} ≥ … ≥ a_{d}, and is said to be log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1}, for i = 1, …, d − 1. It is easy to verify that a positive log-concave sequence is unimodal, though a log-concave sequence need not be (take, e.g., (1, 1, 0, 0, 1, 1)). We say that a polynomial ∑_{i=0}^{d} a_{i} x^{i} is log-concave (respectively, unimodal) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} x^{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 (see, e.g., [15], Thm. B, p.270). Log-concave and unimodal sequence 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, to prove the unimodality or log-concavity of a sequence can 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 symmetric functions, and algebraic geometry. We refer the interested reader to [42] (see also [12]) for a survey of many of these techniques, problems, and results.

The theory of total positivity was first used to attack unimodality problems in 1989 ([5]). In retrospect, this is not too surprising since P F sequences (i.e., Toeplitz T P matrices) are necessarily log-concave and unimodal. Nonetheless, the theory of total positivity was at that time not very well known outside of the fields of probability, statistics, and matrix theory, and thus very few combinatorialists were aware of it. One classical result on P F sequences that proved to be especially useful is the characterization theorem (see, e.g., [24], Theorem 5.3, p. 412).

Theorem 3.1 Let {a_{i}}_{i∈N} be a sequence of real numbers with a_{0} = 1. Then {a_{i}}_{i∈N} is a P F sequence if and only if there exists a ≥ 0 and sequences {α_{i}}_{i∈N}, {β_{i}}_{i∈N} ⊆ R^{+} such that ∑_{i≥0} α_{i} + ∑_{i≥0} β_{i} < +∞ and

∑_{i≥0} a_{i}z^{i} = e^{az} \frac{∏_{i≥0}(1 + α_{i}z)}{∏_{i≥0}(1 − β_{i}z)}  (1)

for all z in some open disc around the origin in the complex plane.

This fundamental result, on which much of the theory of P F sequences is based (see, e.g., [24]), was conjectured by Schoenberg ([39], p.367) and first proved by Edrei ([16], see also [2]). It is interesting to observe that Theorem 3.1 has turned out to be of fundamental importance also in the theory of representations of the infinite symmetric group where it was independently discovered and proved by Thoma ([49], Satz 2).

For the purposes of combinatorics one needs a “formal” version of Theorem 3.1, i.e., one which holds in the ring of formal power series R[[z]] without any question of convergence (note that the RHS of (1) is not a well defined element of R[[z]] since neither ∏_{i≥0}(1 + α_{i}z) nor ∏_{i≥0}(1 − β_{i}z) converge formally in R[[z]] (see, e.g., [41], §1.1, Proposition 1.1.9, p. 6)).

The following consequence of Theorem 3.1 is a restatement of Theorems 4.6.2 and 2.2.4 of [5], and is the result that is actually used in combinatorics.

Theorem 3.2 Let {a_{i}}_{i∈N} be a sequence of real numbers such that

∑_{i≥0} a_{i}x^{i} = \frac{∑_{i=0}^{d}b_{i}x^{i}}{(1 − x)^{d+1}} ,  (2)

in R[[x]], for some d ∈ P and b_{0}, …, b_{d} ∈ R such that ∑_{i=0}^{d} b_{i} ≠ 0. Then the following are equivalent:

i) {a_{0}, a_{1}, a_{2}, …} is a P F sequence;

ii) {b_{0}, …, b_{d}} is a P F sequence;

iii) the polynomial ∑_{i=0}^{d} b_{i}x^{i} has nonnegative coefficients and only real zeros.

There are two main reasons why this particular consequence of Theorem 3.1 is so useful and interesting for combinatorics. The first one is that formal power series of the form (2) are extremely common in enumerative combinatorics. In fact, it is a well known and classical result in the theory of rational generating functions that a formal power series ∑_{i≥0} a_{i}x^{i} is of this form if and only if there exists A(x) ∈ R[x] such that A(i) = a_{i} for all i ∈ N (see, e.g., [41], §4.3, Corollary 4.3.1). Furthermore, it is often the case that if the a_{i}’s have some combinatorial interpretation then the b_{i}’s also do, and conversely, so the equivalence of i) and ii) is often useful. The second reason lies in the fact that there are many polynomials arising in combinatorics that are known (or conjectured) to have only real zeros (see, e.g., [42], §3, p. 504, and [12], §3). This fact has always puzzled and intrigued combinatorialists as they saw no “philosophical” reason why this peculiar analytic phenomenon should occurr so often in combinatorics. However, the equivalence of ii) and iii) in Theorem 3.2 (which, incidentally, was already known before Theorem 3.2, see [17]) shows that the reality of the zeros of a polynomial having nonnegative coefficients is linked to the nonnegativity of certain determinants formed with its coefficients, and this strongly suggests that, in such cases, these determinants should have a combinatorial significance. Thus, combinatorialists were led to the conclusion that, given a combinatorial sequence, it should often be the case that the minors of its associated Toeplitz matrix also “count something”. This was already known in some cases (see, e.g., [30], §I.5, eq. (5.12)), and has stimulated research in this direction, which has produced several beautiful combinatorial results (see, e.g., [19], [9], [36], [43], Corollary 2.9 and the comments following it), conjectures, and open problems.

We now illustrate a particular combinatorial application of Theorem 3.2 and then give references to many others. Let (P, ⪯) be a finite partially ordered set (or, poset, for short). A map φ : P → [i] (i ∈ P) is said to be order preserving if x ⪯ y implies φ(x) ≤ φ(y) for all x, y ∈ P, and is a linear extension if it is order preserving and a bijection (so i = |P |). Given two linear extensions ω, τ : P → [p] (where p =^{def} |P |) we let

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

One can then show (see, e.g., [40], §I.2, p. 6, Definition 3.2, p. 8, and Proposition 8.3, p.24) that the polynomial

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

where the sum is over all linear extensions τ of P, does not depend on ω, but only on P (hence the notation W (P; x) for it). Linear extensions of posets are an important topic both in combinatorics as well as in theoretical computer science, where they are usually called topological sortings (see, e.g., [25], [26], [56]), and the polynomial W (P; x) has been widely studied (see, e.g., [40], [5], [54]). In particular, the following conjecture was made about it in [31].

Conjecture 3.3 Let P be a (finite) poset. Then W (P; x) has only real zeros. In particular, W (P; x) is log-concave and unimodal.

The above conjecture (which was later generalized by Stanley, see [5], §1.2) is open even for the unimodality statement, and has been verified for |P | ≤ 8 (there are 19,449 such posets) ([48], p.5). However, Conjecture 3.3 can be proved in several important cases using Theorem 3.2, thanks to the following result.

Theorem 3.4 Let P be a poset. Then

∑_{i≥0} Ω(P; i)x^{i} = \frac{W (P; x)}{(1 − x)^{|P |+1}}  (5)

in Z[[x]], where

Ω(P; i) = |{f : P → [i] : f is order preserving}|,  (6)

for i ∈ N.

Note that (5) and the remarks following Theorem 3.2 imply that, for a given poset P, Ω(P; i) is a polynomial function of i. The above result was first proved by Stanley in [40], Proposition 8.3, p. 24. We therefore obtain immediately, from Theorems 3.2 and 3.4, the following equivalent conditions for the validity of Conjecture 3.3, which first appeared in [5], §5.7, Theorem 5.7.2.

Theorem 3.5 Let P be a poset. Then the following conditions are equivalent:

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

ii) {w_{0}(P), …, w_{|P |}(P)} is a P F sequence, where w_{i}(P) =^{def} [x^{i}](W (P; x)) for i = 0, …, |P |;

iii) {Ω(P; i)}_{i∈N} is a P F sequence.

Note that since the hard part of Theorem 3.2 is the implication i) ⇒ iii) it is reasonable to expect that proving iii) should be easier than proving i), in Theorem 3.5. This is also confirmed by the fact that the combinatorial meaning of Ω(P; i) (see (6)) is simpler than that of w_{i}(P) (see (3), (4), and part ii) of Theorem 3.5). In fact, for many classes of posets one knows formulas for Ω(P; i), but not for w_{i}(P) (see, e.g., [5], §§5.2, 5.4, 5.5, and 5.6). However, even these known formulas do not make it clear whether the sequence {Ω(P; i)}_{i∈N} is P F or not. This led combinatorialists to study sufficient conditions (usually suggested by the known formulas for Ω(P; i)) for a sequence to be P F, and eventually led to the following result. Given a polynomial A(x) ∈ R[x], having only real zeros, we denote by λ(A) (respectively Λ(A)) its smallest (respectively, largest) zero.

Theorem 3.6 Let A(x) ∈ R[x] be a polynomial having only real zeros. Suppose that A(x) = 0 for all x ∈ {(λ(A), −1] ∪ [0, Λ(A))} ∩ Z. Then the sequence {A(i)}_{i∈N} is P F.

The above result (which actually holds under slightly milder hypotheses, see [5], Theorem 4.3.4) was first proved in [5], see Theorem 4.4.1. It is worth noting that, even though it was motivated by purely combinatorial reasons, Theorem 3.6 is a result on total positivity, with no combinatorics in it. This theme of combinatorics stimulating results in total positivity, and conversely, will come up again and again in this survey, and is in fact its main message.

Using Theorem 3.6 it is indeed possible to prove Conjecture 3.3 in many interesting cases, for example for Gaussian posets, disjoint unions of chains, and certain Ferrers posets (we refer the reader to [5], Chapter 5, for the definitions of these classes of posets and further details). In each case, the proof follows immediately from known formulas for Ω(P; i) using Theorems 3.5 and 3.6.

If P_{1} and P_{2} are posets then one can form their disjoint union P_{1} ⊎ P_{2} (see, e.g., [41], §3.2, for a discussion of this and other operations on posets). It is then well known, and easy to see from (6), that

Ω(P_{1} ⊎ P_{2}; i) = Ω(P_{1}; i) Ω(P_{2}; i)

for all i ∈ N. Thus Theorem 3.5 and Conjecture 3.3 naturally lead to the question of whether the Hadamard (i.e., componentwise) product of two P F sequences is again P F. It was already known to Karlin (see also [5], §6.5, p. 77, for an explicit example) that this is in general false, though it is true for eventually vanishing sequences (see, e.g., [5], Theorem 4.7.8). However, as noted after Theorem 3.4, the sequence {Ω(P; i)}_{i∈N} has the special property that Ω(P; i) is a polynomial function of i. Combinatorialists tried to find out if this particular question had been considered before (see, e.g., [4], and [5], §4.7, p. 55), then studied it themselves (see, [5], §4.7), and were finally led to the following result (see, [52], and [53], Theorem 0.3).

Theorem 3.7 Let A(x), B(x) ∈ R[x] be such that {A(i)}_{i∈N} and {B(i)}_{i∈N} are P F sequences. Then {A(i)B(i)}_{i∈N} is a P F sequence.

Once again, this is a total positivity result that was motivated purely from combinatorics. Just as for Theorem 3.6, Theorem 3.7 has also many consequences in combinatorics, and allows the proof of Conjecture 3.3 in other interesting cases such as for trees and series-parallel posets. All these applications are described in detail in [54]. Though Theorems 3.6 and 3.7 were motivated by Conjecture 3.3, they have found many other applications in combinatorics. For a description of some of these we refer the reader to [5], Chapter 6, and [53].

But there are more developments in total positivity that have arisen from Theorems 3.6 and 3.7. A closer look at (5) reveals what is really going on. Let A(x) ∈ R[x] and write

A(x) = ∑_{i=0}^{d} a_{i} (\begin{matrix}x+d−i \\ d \end{matrix})

where d =^{def} deg(A). Then an easy application of the binomial theorem (see, e.g., [41], p. 16) implies that

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

in R[[x]]. Therefore, by Theorem 3.2, the statement “{A(i)}_{i∈N} is a P F sequence” is equivalent to “{a_{0}, …, a_{d}} is a P F sequence”, and the relationship between Ω(P; i) and W (P; x) is really that of expanding Ω(P; x) (considered as a polynomial in x) in terms of the basis (\begin{matrix}x+d−i \\ d \end{matrix}) (where d =^{def} deg(Ω(P; x))) and then changing (\begin{matrix}x+d−i \\ d \end{matrix}) to x^{i}, for i = 0, …, d.

These considerations lead naturally to the following definitions and general problems. Let {v_{i}(x)}_{i=0,...,d} be an ordered basis of V_{d}. Define, for r ∈ P ∪ {∞},

P F_{r}[v_{i}] =^{def} {∑_{i=0}^{d} a_{i}v_{i}(x) ∈ R[x] : {a_{0}, …, a_{d}} is a P F_{r} sequence }

and let P F [v_{i}] =^{def} P F_{∞}[v_{i}], for brevity. Then Theorem 3.6 can be interpreted as giving a sufficient condition for a polynomial in P F [x^{i}] to be also in P F [(\begin{matrix}x+d−i \\ d \end{matrix})]. Thus, one may ask if similar results exist for other pairs of bases of V_{d}. Indeed, often one does not even need any extra conditions, as the following result shows (see [5], Chapter 2, Theorems 2.6.1, 2.6.2, and 2.6.3).

Theorem 3.8 Let d ∈ P. Then the following strict inclusions hold:

P F [((\begin{matrix}x \\ i \end{matrix}))] ⊂ P F [⟨x⟩_{i}] ⊂ P F [x^{i}] ⊂ P F [(x)_{i}],

P F [(\begin{matrix}x+d−i \\ d \end{matrix})] ⊂ P F [(\begin{matrix}x \\ i \end{matrix})] ⊂ P F [(x)_{i}],

P F_{2} [((\begin{matrix}x \\ i \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}],

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

Sometimes, simple conditions suffice, (see [5], Theorem 3.2.1).

Theorem 3.9 Let A(x) ∈ R[x] be a polynomial of degree d. Then the following are equivalent:

i) A(x) ∈ P F [(\begin{matrix}x \\ i \end{matrix})] ∩ P F_{1} [(\begin{matrix}x+d−i \\ d \end{matrix})];

ii) {A(i)}_{i∈N} is a P F sequence.

The preceding result can equivalently be stated as saying that P F [(\begin{matrix}x \\ i \end{matrix})]∩P F_{1} [(\begin{matrix}x+d−i \\ d \end{matrix})] = P F [(\begin{matrix}x+d−i \\ d \end{matrix})] for all d ∈ P. Theorems 3.8 and 3.9, though not motivated directly by combinatorics, have also found numerous applications in enumerative combinatorics (see [5], Chapter 6, [6], [7]).

Note that Theorem 3.7 can be restated, by Theorem 3.2 and the remarks follow-

ing Theorem 3.7, as the assertion that “P F [(\begin{matrix}x+d−i \\ d \end{matrix})] P F [(\begin{matrix}x+e−i \\ e \end{matrix})] ⊆ P F [(\begin{matrix}x+d+e−i \\ d+e \end{matrix})]”

(where, for A, B ⊆ V_{d}, AB =^{def} {ab : a ∈ A, b ∈ B}). Since it follows from Theorem 3.2 that P F [x^{i}]P F [x^{i}] ⊆ P F [x^{i}], it is natural to wonder whether similar “product theorems” hold for some of the other bases considered in Theorem 3.8. Indeed, the following holds, (see Proposition 4.2 and 4.4 in [10], and Theorem 4.5 and the formula at the top of page 153 in [51]).

Theorem 3.10 P F [(x)_{i}]P F [(x)_{i}] ⊆ P F [(x)_{i}].

On the other hand P F [⟨x⟩_{i}]P F [⟨x⟩_{i}] ⊈ P F_{1}[⟨x⟩_{i}] since, for example, ⟨x⟩(1+2⟨x⟩) =

2⟨x⟩_{2} − ⟨x⟩, and therefore P F [((\begin{matrix}x \\ i \end{matrix}))] P F [((\begin{matrix}x \\ i \end{matrix}))] ⊈ P F_{1} [((\begin{matrix}x \\ i \end{matrix}))] also.

Note that Theorems 3.2, 3.7, 3.8, 3.9, and 3.10 all have as underlying theme the study of linear transformations that preserve the P F or P F_{2} property of a sequence. This topic had been studied before in total positivity (see, e.g., [24], Theorem 7.3, p. 142) but not in such detail. Nonetheless, several open problems and conjectures remain in the area, and we survey the main of these in section 6.

4 T P matrices in combinatorics

The applications of total positivity to combinatorics described in the previous section , and the total positivity results that were obtained with (direct or indirect) motivation from combinatorics, all deal with P F sequences (i.e., Toeplitz T P matrices). After these results were obtained it was slowly realized that T P matrices themselves are in fact quite ubiquitous in combinatorics. In this section we survey the main results in this direction.

In retrospect, the first result of this kind was obtained by B. Lindström ([28]) though he did not state it at all in the language of total positivity, and in fact just used it as a lemma to prove a result in matroid theory. To describe Lindström’s result we now require a little bit of notation and terminology. Let D = (V, A) be a directed graph (or, digraph, for short). We will always assume that D has no loops or multiple edges, so that we can identify the elements of A with ordered pairs (u, v), with u, v ∈ V, u ≠ v. A path in D is a sequence π = u_{1}u_{2} … u_{n} of elements of V such that (u_{i}, u_{i+1}) ∈ A for i = 1, …, n − 1, we then say that π goes from u_{1} to u_{n}. We say that D is locally finite if, for every u, v ∈ V, there are only a finite number of paths from u to v. Note that this implies that D is acyclic. We say that D is weighted if there is a function w : A → R, where R is some commutative Q-algebra. If R = R and w((u, v)) ≥ 0 for all (u, v) ∈ A then we call D a nonnegative digraph. Let D = (V, A, w) be a locally finite, weighted, digraph. For a path π = u_{0}u_{1} … u_{k} in D we let

w(π) =^{def} ∏_{i=1}^{k} w(u_{i−1}, u_{i}) ,

and, for u, v ∈ V, we let

P_{D}(u, v) =^{def} ∑_{π} w(π) ,

where the sum is over all paths π in D going from u to v. We adopt the convention that P_{D}(u, u) =^{def} 1 for all u ∈ V (i.e. there is only one path, the empty path, from u to u and its weight is 1). We will usually omit the subscript D when there is no danger of confusion. Given u =^{def} (u_{1}, …, u_{r}), v =^{def} (v_{1}, …, v_{r}) ∈ V^{r} we let

N(u, v) =^{def} ∑_{(π_{1},...,π_{r})} w(π_{1}, …, π_{r}) ,

where w(π_{1}, …, π_{r}) =^{def} ∏_{i=1}^{r} w(π_{i}), and where the sum is over all r-tuples of paths (π_{1}, …, π_{r}) from u to v (i.e., π_{i} is a path from u_{i} to v_{i}, for i = 1, …, r) that are non-intersecting (i.e., π_{i} and π_{j} have no vertices in common if i ≠ j). We say that u and v are compatible if, for every σ ∈ S_{r} \ {Id}, there are no r-tuples of paths from (u_{1}, …, u_{r}) to (v_{σ(1)}, …, v_{σ(r)}) that are non-intersecting. The following fundamental result was first proved by Lindström in [28].

Lemma 4.1 (Lindström’s Lemma) Let D = (V, A, w) be a locally finite, weighted digraph and u =^{def} (u_{1}, …, u_{n}), v =^{def} (v_{1}, …, v_{n}) ∈ V^{n} be compatible. Then

N(u, v) = det [(P_{D}(u_{i}, v_{j}))_{1≤i, j≤n}] .  (7)

We refer the reader to [19], Corollary 2, [44], Theorem 1.2, or [28], Lemma 1 for the proof of Lemma 4.1. We should mention that a reasoning very similar to the one used by Lindström to prove his lemma had been used previously by Karlin and McGregor in [23], though there is no doubt that Lindström was unaware of their work.

The importance of Lindström’s Lemma in the discovery and proof that many matrices arising in combinatorics are T P can hardly be overestimated, as all of these proofs use this result, either implicitly or explicitly. The first notable application of Lindström’s Lemma in this direction was given by Gessel and Viennot in [18] where they construct a directed graph that enables them to give a combinatorial interpretation of any minor of the infinite matrix of binomial coefficients, and many other applications in enumerative and algebraic combinatorics followed (see, e.g., [9], [19], [36], [44]).

Aside from its direct applications to combinatorial matrices, Lindström’s Lemma also turned out to be extremely important from a theoretical point of view. It is easy to see (see [13], Figure 1, for a specific example) that the matrix on the RHS of (7) is in general not T P under the hypoteses of Lemma 4.1. However, if we define two r-tuples of vertices (u_{1}, …, u_{r}) and (v_{1}, …, v_{r}) of D to be fully compatible if (u_{i_{1}}, …, u_{i_{k}}) is compatible to (v_{i_{1}}, …, v_{i_{k}}) for all 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ r then it is clear that we can apply Lindström’s Lemma to any minor of (P_{D}(u_{i}, v_{j}))_{1≤i,j≤n} and hence conclude that it is totally positive if D is nonnegative. What is extremely surprising, however, is that the converse statement also holds. Namely, we have the following result.

Theorem 4.2 Let U be an n × n (real) matrix. Then U is totally positive if and only if there exists a planar, finite, nonnegative digraph D = (V, A, w), and u= (u_{1}, …, u_{n}), v = (v_{1}, …, v_{n}) ∈ V^{n} fully compatible, such that

U = (P_{D}(u_{i}, v_{j}))_{1≤i, j≤n} .  (8)

The preceding result was first explicitly stated and proved in [13], Theorem 3.1. Note that Theorem 4.2 makes some well known properties of T P matrices obvious.

For example, it immediately implies that the product of two T P matrices is again T P. A less obvious consequence is the following one, which had been conjectured by Stembridge ([47]) and first proved by him in [45], though not using Theorem 4.2. Recall that given a partition λ of n and an n × n matrix A = (a_{i,j})_{1≤i,j≤n} the immanant of A with respect to λ is

Imm_{λ}(A) =^{def} ∑_{σ∈S_{n}} χ_{λ}(σ)a_{1,σ(1)} … a_{n,σ(n)}

where χ_{λ} : S_{n} → Q is the irreducible character of S_{n} corresponding to the partition λ (we refer the reader to, e.g., [38], for further information on the irreducible characters of S_{n}). Note that if l(λ) = n then χ_{λ}(σ) = sgn(σ) for all σ ∈ S_{n} and hence Imm_{λ}(A) = det(A), while if l(λ) = 1 then χ_{λ}(σ) = 1 for all σ ∈ S_{n} and hence Imm_{λ}(A) = per(A).

Theorem 4.3 Let A be an n × n (real) totally positive matrix. Then

Imm_{λ}(A) ≥ 0

for all partitions λ of n.

For a proof of Theorem 4.3 based on Theorem 4.2 see [13], Corollary 3.8.

Despite the fact that Theorem 4.2 describes all the totally positive matrices, it can sometimes be a difficult task, given a T P matrix U, to construct a digraph D and u, v fully compatible such that (8) holds. Thus, the usefulness of Theorem 4.2 for actually proving that certain matrices are T P can be limited. Nonetheless, there are other general results that can be proved using Lindström’s Lemma that are easier to apply than Theorem 4.2. Let x =^{def} {x_{n}}_{n∈N}, y =^{def} {y_{n}}_{n∈N}, and z =^{def} {z_{n}}_{n∈N} be three sequences of independent variables. We will adopt the convention that x_{n} =^{def} y_{n} =^{def} z_{n} =^{def} 0 if n < 0.

Theorem 4.4 Let t ∈ N. Define a matrix M = (M_{n,k})_{n,k∈N} by

M_{n,k} = z_{n} M_{n−t,k−1} + y_{n} M_{n−1−t,k−1} + x_{n} M_{n−1,k}  (9)

if n + k ∈ P (where M_{n,k} =^{def} 0 if either n < 0 or k < 0), and M_{0,0} =^{def} 1. Then:

i) M is (x, y, z)-totally positive;

ii) every row of M is an (x, y, z)-PF sequence.

In what follows we denote by M_{t}(x, y, z) the matrix defined in the preceding theorem. Theorem 4.4 (which is proved in [13], Theorem 4.3) immediately implies the T P property for an impressive array of matrices arising in enumerative and algebraic combinatorics, as we now show.

For n, k ∈ N let S[n, k]_{p,q} and c[n, k]_{p,q} be the (p, q)-Stirling numbers of the second and first kind, respectively. These are defined inductively by letting

S_{p,q}[n, k] = p^{k−1} S_{p,q}[n − 1, k − 1] + [k]_{p,q} S_{p,q}[n − 1, k] ,

and

c_{p,q}[n, k] = p^{n} c_{p,q}[n − 1, k − 1] + q[n − 1]_{q} c_{p,q}[n − 1, k] ,

if n + k ∈ P (with the convention that S_{p,q}[n, k] =^{def} c_{p,q}[n, k] =^{def} 0 if either n < 0 or k < 0), and S_{p,q}[0, 0] =^{def} c_{p,q}[0, 0] =^{def} 1. (We refer the reader to [50] and [13] for combinatorial interpretations and further information about these polynomials). It then follows immediately from these definitions and from (9) that

(S_{p,q}[n + 1, k + 1])_{n,k∈N} = M_{0}(0, {p^{n}}_{n∈N}, {[n + 1]_{p,q}}_{n∈N})′ ,  (10)

and

(c_{p,q}[n + 1, k + 1])_{n,k∈N} = M_{0}({q[n]_{q}}_{n∈N}, {p^{n+1}}_{n∈N}, 0) .  (11)

For n, k ∈ N let

[\begin{matrix}n \\ k \end{matrix}]_{q} =^{def} ∏_{i=1}^{k} \frac{(1 − q^{n−i+1})}{(1 − q^{i})} .  (12)

Then it is easy to see that

([\begin{matrix}n+k \\ k \end{matrix}]_{q})_{n,k∈N} = M_{0}(1, 0, \{q^{n}\}_{n∈N})′ .

For n, k ∈ N let \overline{S}[n, k]_{p,q}, Ŝ[n, k]_{p,q}, and S̃[n, k]_{p,q} be the (p, q)-Stirling numbers of the second kind defined in §6 of [37] (to which we refer the reader for their definition). (Note that what we denote by \overline{S}[n, k]_{p,q} is denoted by S[n, k]_{p,q} in §6 of [37]). Then it follows from the results in [37] and from (9) that

(\overline{S}[n + 1, k + 1]_{p,q})_{n,k∈N} = M_{0}(0, 1, \{1 + pq[k]_{p,q}\}_{k∈N})′ ,
(Ŝ[n + 1, k + 1]_{p,q})_{n,k∈N} = M_{0}(0, {q^{k}}_{k∈N}, {[k + 1]_{p,q}}_{k∈N})′ ,

and

(S̃[n + 1, k + 1]_{p,q})_{n,k∈N} = M_{0}(0, {q^{k}}_{k∈N}, {q^{k} + p[k]_{qp}}_{k∈N})′ .

For n, k ∈ N let S_{B}(n, k; q) be the q-Stirling number of the second kind of type B_{n} defined in §3 of [11]. These may also be defined by

S_{B}(n, k; q) = ∑_{i=k}^{n} (\begin{matrix}n \\ i \end{matrix}) q^{n−i}(1 + q)^{i} S(i, k) ,  (13)

and have the property that S_{B}(n, k; 0) = S(n, k), while k! S_{B}(n, k; 1) equals the number of k-dimensional faces of the Coxeter complex of type B_{n} (see, e.g., [11], §3, for further details). Then it follows from eq. (41) on p. 430 of [11] that

(S_{B}(n, k; q))_{n,k∈N} = M_{0}(0, (1 + q)1, {k(1 + q) + q}_{k∈N})′ .

For n, k, r ∈ P let D_{r}(n, k) be the set of all σ ∈ S_{n} that have exactly k cycles, each of size ≥ r. Note that |D_{1}(n, k)| is just the signless Stirling number of the first kind c(n, k), while |D_{2}(n, k)| is the number of derangements of S_{n} having k cycles, (these numbers are sometimes called the Jordan numbers, see, e.g., [14]). The numbers |D_{r}(n, k)| are usually called the signless r-associated Stirling numbers of the first kind (see, e.g., [15], p. 257, Ex. 7, for further information about these numbers). For n, k ∈ N let c_{r}[n, k]_{q} be the r-associated signless q-Stirling numbers of the first kind defined in §5 of [13] (to which we refer the reader for their definition). It can be shown that c_{1}[n, k]_{q} = c[n, k], where c[n, k] denotes a q-Stirling number of the first kind as defined, e.g., in [27], and that c_{r}[n, k]_{1} = |D_{r}(n, k)|. Then it follows from Theorem 5.7 of [13] that

(c_{r}[n, k]_{q})_{n,k∈N} = M_{r} ({[n − 1]_{q}}_{n∈N}, 0, {q^{r−1} ∏_{i=1}^{r−1}[n − i]_{q}}_{n∈N}) .

For n, k ∈ N let D(n, k) be the Delannoy number. This can be defined by

D(n, k) =^{def} ∑_{i=0}^{k} (\begin{matrix}k \\ i \end{matrix}) (\begin{matrix}n+k−i \\ k \end{matrix}) ,  (14)

(see, e.g., [15], p.81, for the combinatorial significance of these numbers). Then it is easy to see that

(D(n, k))_{n,k∈N} = M_{0}(1, 1, 1)′ .  (15)

For k, n ∈ N let a(n, k) be the number of regions into which n hyperplanes in general position divide R^{k}, (see, e.g., [57] for further information on hyperplane arrangements). Then it follows from [15], p. 72, Ex. 2, and from (9) that

(a(n, k))_{n,k∈N} = M_{0}(1, 1, {1, 0, 0, …}) .

For n, k ∈ N let L[n, k]_{q} be the signless q-Lah numbers defined in §5 of [13]. For q ∈ P the L[n, k]_{q} were first defined and studied in [1] where they arose from a problem in statistics and where they are called the associated Lah numbers. It can be shown that L[n, k]_{q} reduces to the absolute value of the ordinary Lah number L(n, k) (as defined, e.g., in [15], p.135) when q = 1. Then it follows from results in [1] (see also [13], Theorems 4.8, and 5.17) and from (9) that

(L[n, k]_{q})_{n,k∈N} = M_{0}({0, 0, 1, 2, …}, 1, 0) M_{0}(0, q1, {nq}_{n∈N})′ .

It should be noted that the proof of Theorem 4.4 (see [13], Theorems 4.3 and 4.1) actually gives a combinatorial interpretation of the minors involved in i) and ii), which can then be specialized to obtain more explicit combinatorial interpretations in the special cases considered above. This has been carried out in detail in [9] for the matrices in (11) and (10) when p = 1, but has not been done yet in other cases. Theorem 4.4 is not an isolated result and similar ones appear in §4 of [13].

Despite the large applicability of Theorem 4.4 there are still many matrices arising in enumerative combinatorics which are only conjectured to be T P, we survey the main open problems in this area in section 6.

5 Recent Developments

In recent years there has been a growing trend in enumerative and algebraic combinatorics to extend classical results known for permutations (i.e., for the symmetric group) to other Coxeter groups (see, e.g., [11], [33], [34], [35]). The concept of total positivity has been no exception, and in this section we describe these new developments.

We require first some notation, terminology, and definitions. Let, for brevity, E =^{def} R^{n}, and denote by (,) its usual inner product. Given α ∈ E \ {0} we denote by H_{α} the hyperplane orthogonal to α (i.e., H_{α} =^{def} {v ∈ E : (v, α) = 0}) and by σ_{α} the orthogonal reflection through H_{α} (i.e., the only linear transformation of E into itself that fixes H_{α} pointwise, and sends α to −α). In other words,

σ_{α}(x) = x − \frac{2(x, α)}{(α, α)}α

for all x ∈ E. A (finite) subset Δ ⊆ E is said to be a root system if the following conditions are satisfied: i) Δ spans E, and 0 ∉ Δ;

ii) if α, β ∈ Δ and α = cβ for some c ∈ R then c ∈ {1, −1};

iii) σ_{α}(Δ) = Δ for all α ∈ Δ;

iv) if α, β ∈ Δ then \frac{2(α,β)}{(α,α)} ∈ Z.

The elements of Δ are called the roots of Δ. A root system is called irreducible if there are no Δ_{1}, Δ_{2} ⊆ Δ, Δ_{1}, Δ_{2} ≠ ∅, such that Δ = Δ_{1} ∪ Δ_{2}, Δ_{1} ∩ Δ_{2} = ∅ and (α, β) = 0 for all α ∈ Δ_{1} and β ∈ Δ_{2}.

A subgroup W of GL(E) is called a finite reflection group (or a Coxeter group) if there exists a root system Δ ⊆ E such that W equals the subgroup of GL(E) generated by {σ_{α} : α ∈ Δ}. We say that W is irreducible if Δ is irreducible. Note that since σ_{α}(Δ) = Δ and σ_{α} is invertible, σ_{α} permutes Δ and σ_{α} is determined by σ_{α|Δ} since Δ spans E. Hence we may identify W as a subgroup of the symmetric group on Δ which shows, in particular, that W is indeed finite. Irreducible finite reflection groups have been completely classified (see, e.g., [22], Chapter 2, for an excellent exposition of this classification). It turns out that there are five infinite families, usually denoted by A_{n}, B_{n}, C_{n}, D_{n}, and I_{2}(n) (n ∈ P, n ≥ 2) and seven single groups, usually denoted by E_{6}, E_{7}, E_{8}, F_{4}, G_{2}, H_{3}, and H_{4}.

Now let A =^{def} E \ ⋃_{α∈Δ} H_{α}. Clearly, the connected components of A (which are called Weyl chambers) are convex open cones. Fix, once and for all, a Weyl chamber C, and call it the fundamental chamber. The following result is fundamental, and a proof of it can be found, e.g., in [22], Theorem 1.12.

Theorem 5.1 W acts on A and this action is simply transitive, (i.e., given two Weyl chambers C_{1} and C_{2} there exists a unique w ∈ W such that w(C_{1}) = C_{2}). In particular, there is a unique bijection between the set of Weyl chambers and W such that C corresponds to the identity in this bijection.

Now let e_{1}, …, e_{n} be the canonical basis of E = R^{n} (i.e., e_{i} = (0, …, 0, \overbrace{1}^{i}, 0, …, 0), for i = 1, …, n). Given x ∈ R^{n} we denote by x_{j} its j-th coordinate with respect to this basis (so that x = (x_{1}, …, x_{n})). We are now ready to define the crucial concepts of this section which are due to K. Gross and D. St. P. Richards ([21]). Given a function K : R^{2} → R we let

D_{W} K(s, t) =^{def} ∑_{w∈W} det(w) ∏_{j=1}^{n} K(s_{j}, w(t)_{j})  (16)

for each s, t ∈ R^{n}. We say that K is W -totally positive (or W − T P, for brevity) if

D_{W} K(s, t) ≥ 0  (17)

for all s, t ∈ C. We say that K is W -symmetric if

D_{W} K(s, w(t)) = D_{W} K(w(s), t)

for all s, t ∈ R^{n} and w ∈ W, and denote by H the class of all W -symmetric functions K : R^{2} → R.

The most basic result on totally positive functions is that the convolution of two totally positive functions is again totally positive (see, e.g., [24]). This extends to W -total positivity (see [21], Theorem 3.5).

Theorem 5.2 Let L, M ∈ H be W -totally positive and suppose that

K(x, y) =^{def} ∫_{R} L(x, z)M(z, y)dz

converges absolutely for any (x, y) ∈ R^{2} (where dz denotes Lebesgue measure). Then K ∈ H and K is W -totally positive.

In order to better understand the concept of W -total positivity (which would otherwise be rather abstract) it is useful to look at some important special cases. We will analyze the concept of W -total positivity for the four infinite families A_{n}, B_{n}, C_{n}, and D_{n}.

For type A_{n} it can be shown (see [21], §6) that a function K : R^{2} → R is A_{n}- totally positive for n = 1, …, r if and only if it is T P_{r} in the classical sense and that any function K : R^{2} → R is W -symmetric for type A_{n} for all n ≥ 2. Thus we will not spend any more words on this case. Also, it is not hard to show from the definitions and known facts on finite reflection groups that the concepts of B_{n}-total positivity and C_{n}-total positivity are equivalent for any n ≥ 2.

For type B_{n} it is known (see, e.g., [22], §2.10) that a finite reflection group W of type B_{n} can be realized by taking

Δ =^{def} {±e_{i} ± e_{j} : 1 ≤ i < j ≤ n} ∪ {±e_{i} : i ∈ [n]}

and E =^{def} R^{n}, and that W then equals the set of all n × n signed permutation matrices (i.e., matrices of the form P diag(ε_{1}, …, ε_{n}) where P is a permutation matrix and ε_{1}, …, ε_{n} ∈ {−1, 1}). As a fundamental chamber we may take

C = {x ∈ R^{n} : 0 < x_{1} < x_{2} < … < x_{n}}.

In this case we obtain from (16) that

D_{W} K(s, t) = ∑_{ε∈{−1,1}^{n}} ∑_{σ∈S_{n}} (∏_{j=1}^{n} ε_{j}) sgn(σ) ∏_{j=1}^{n} K(s_{j}, ε_{σ(j)}t_{σ(j)})
= ∑_{ε∈{−1,1}^{n}} (∏_{j=1}^{n} ε_{j}) det[K(s_{i}, ε_{j}t_{j})_{1≤i,j≤n}]

for any K : R^{2} → R and s, t ∈ R^{n}. Hence K is W -totally positive in this case if and only if

∑_{ε_{1},...,ε_{n}∈{−1,1}} (∏_{j=1}^{n} ε_{j}) det[K(s_{i}, ε_{j}t_{j})_{1≤i,j≤n}] ≥ 0

for all 0 < s_{1} < … < s_{n} and 0 < t_{1} < … < t_{n}. For example, if W is of type B_{2} then K is W − T P if and only if

det [ \begin{matrix}K(s_{1}, t_{1}) & K(s_{1}, t_{2}) \\ K(s_{2}, t_{1}) & K(s_{2}, t_{2}) \end{matrix} ] + det [ \begin{matrix}K(s_{1}, −t_{1}) & K(s_{1}, −t_{2}) \\ K(s_{2}, −t_{1}) & K(s_{2}, −t_{2}) \end{matrix} ] ≥

det [ \begin{matrix}K(s_{1}, −t_{1}) & K(s_{1}, t_{2}) \\ K(s_{2}, −t_{1}) & K(s_{2}, t_{2}) \end{matrix} ] + det [ \begin{matrix}K(s_{1}, t_{1}) & K(s_{1}, −t_{2}) \\ K(s_{2}, t_{1}) & K(s_{2}, −t_{2}) \end{matrix} ]

for all 0 < s_{1} < s_{2} and 0 < t_{1} < t_{2}. No characterization is known of the functions K : R^{2} → R that are W -symmetric in this case. However, it is not hard to check that if K(s, −t) = K(−s, t) for all s, t ∈ R then K is W -symmetric for type B_{n}, for all n ≥ 2.

For type D_{n} it is known (see, e.g., [22], §2.10) that a finite reflection group W of type D_{n} can be realized by taking

Δ =^{def} {±e_{i} ± e_{j} : 1 ≤ i < j ≤ n}

and E =^{def} R^{n}, and that W then equals the set of all n × n signed permutation matrices that have an even number of negative entries (i.e., matrices of the form P diag(ε_{1}, …, ε_{n}) where P is a permutation matrix, ε_{1}, …, ε_{n} ∈ {−1, 1}, and ∏_{j=1}^{n} ε_{j} = 1). As a fundamental chamber we may take

C = {x ∈ R^{n} : |x_{1}| < x_{2} < … < x_{n}}.

In this case we obtain from (16) that

D_{W} K(s, t) = _{{ε∈{−1,1}^{n}:∏_{j=1}^{n} ε_{j}=1}}^{∑} det[K(s_{i}, ε_{j}t_{j})_{1≤i,j≤n}]

for any K : R^{2} → R and s, t ∈ R^{n}. Hence, by (17), K is W -totally positive in this case if and only if

∑_{{ε_{1},...,ε_{n}∈{−1,1}: ε_{1}...ε_{n}=1}} det[K(s_{i}, ε_{j}t_{j})_{1≤i,j≤n}] ≥ 0  (18)

for all |s_{1}| < s_{2} < … < s_{n} and |t_{1}| < t_{2} < … < t_{n}. It is again true that if K(s, −t) = K(−s, t) for all s, t ∈ R then K is W -symmetric for W of type D_{n} for all n ≥ 2.

We hope that these cases will have helped the reader get a feeling for these new concepts of total positivity. The notions described in this section have been developed very recently in [21] and their study is still in its infancy. We discuss some conjectures and open problems on W -total positivity in the next section.

Before closing this section we should mention that yet another generalization of the concept of total positivity has recently been developed by G. Lusztig in [29]. Lusztig defines the concept of total positivity for any element of a split reductive connected (real) algebraic group, and obtains usual total positivity when the group is GL(n; R).

6 Conjectures and Open Problems

Despite the spectacular applications between total positivity and combinatorics surveyed in this paper an impressive array of open problems and conjectures, both of a total positivity as well as of a combinatorial nature, still remain. In this section we describe some of the most outstanding ones and give references to others.

We begin with some total positivity problems that arise naturally from the results described in section 3. Theorem 3.8 gives inclusions that hold between the classes P F [v_{i}] and P F_{2}[v_{i}] as {v_{i}}_{i=0,...,d} ranges over certain bases of V_{d}. It is shown in the Appendix on p. 103 of [5] that these are all the possible inclusions except possibly for one, which is the following.

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

The answer is yes if d ≤ 5.

In addition to the six bases in Theorem 3.8 there are other bases that one may wish to consider, though their choice will depend on the applications that one has in mind. Though not directly related to combinatorics, two bases worth looking at are those consisting of the Eulerian and Krawtchouk polynomials. The Eulerian polynomials A_{i}(x) may be defined inductively by letting A_{0}(x) =^{def} 1 and

A_{n}(x) =^{def} (1 + (n − 1)x)A_{n−1}(x) + (x − x^{2})\frac{d}{dx}(A_{n−1}(x))  (19)

for n ≥ 1 (see, e.g., [15], for the combinatorial significance and further information about the Eulerian polynomials).

Conjecture 6.2 P F [A_{i}(x)] ⊆ P F [x^{i}].

Note that the conjecture states that if the polynomial ∑_{i=0}^{d} k_{i}x^{i} has only real zeros and nonnegative coefficients then the polynomial ∑_{i=0}^{d} k_{i}A_{i}(x) also does. The Krawtchouk polynomials may be defined by

K_{i}^{(d)}(x) =^{def} ∑_{j=0}^{i}(−2)^{j} (\begin{matrix}d−j \\ i−j \end{matrix} ) (\begin{matrix}x \\ j \end{matrix}) .

Conjecture 6.3 P F [K_{i}^{(d)}(x)] ⊆ P F [(−1)^{i}x^{i}].

These two conjectures first appeared in [5], §3.4. Another conjecture similar to the last two, but involving the Lagrange interpolation polynomials appears in [5], §3.4, p. 33.

The following problem is naturally suggested by Theorem 3.10 and the comments preceding and following it.

Problem 6.4 Is it true that P F [(\begin{matrix}x \\ i \end{matrix})] P F [(\begin{matrix}x \\ i \end{matrix})] ⊆ P F [(\begin{matrix}x \\ i \end{matrix})]?

Regarding combinatorial problems involving total positivity, Conjecture 3.3 is certainly one of the most outstanding, but problems of a similar nature abound (see, e.g., [42], §3, [12], §4, [6], §6, [7], §7, [11], §5, [8], §5, [10], §6). We will just mention two of them here to give to the reader an idea of their nature.

Let G = (V, E) be a graph (i.e., V is a finite set and E ⊆ (\begin{matrix}V \\ 2 \end{matrix} )). A function f : V → P is called a coloring of G if φ(x) ≠ φ(y) for all x, y ∈ V such that (x, y) ∈ E. Given n ∈ P we denote by P_{G}(n) the number of colorings φ : V → P such that φ(V) ⊆ [n]. It is then well known (see, e.g., [15], §4.1, p. 179, ex. (2)) that there exists a polynomial χ(G; x) ∈ Z[x] of degree |V | such that χ(G; n) = P_{G}(n) for all n ∈ P. This polynomial is called the chromatic polynomial of G and has been studied extensively (see, e.g., [32], and the references cited there).

Conjecture 6.5 Let G be a graph. Then {χ(G; n)}_{n∈N} is a P F_{2} sequence.

Conjecture 6.6 Let G be a graph. Then (−1)^{p}χ(G; −x) ∈ P F [(x)_{i}], where p =^{def} |V |.

Conjecture 6.5 first appeared in [7], see Conjecture 7.5. Conjecture 6.6 first appeared in [55], has been verified for all graphs with |V | ≤ 9 and is known to be true in several cases (see [7], p. 751, and [10], §5).

We now examine some total positivity problems arising from the results presented in section 4. There are (at least) two major problems that are naturally suggested by Theorem 4.2.

Problem 6.7 Can Theorem 4.2 be generalized to infinite matrices U = (U_{i,j})_{i,j∈N}?

Problem 6.8 Can Theorem 4.2 be generalized to (finite) x − T P matrices?

On a more specific level, the following conjecture (which would trivially imply Theorem 4.3) is particularly intriguing.

Conjecture 6.9 Let M be a T P_{r}-matrix (r ∈ P). Then Imm_{λ}(M) ≥ 0 for all partitions λ such that l(λ) ≤ r.

The preceding conjecture is due to J. Stembridge ([46]), and is open even for r = 2.

We mentioned in section 4 that despite the power of Theorems 4.2 and 4.4 many matrices arising from combinatorics are only conjectured to be T P. We give here two such examples. Let A(n, k) =^{def} [x^{k}](A_{n}(x)) (where A_{n}(x) is the n-th Eulerian polynomial, defined by (19)) for k, n ∈ N. The numbers A(n, k) are called Eulerian numbers and have been widely studied in combinatorics (see, e.g., [15], §6.5).

Conjecture 6.10 The matrix A =^{def} (A(n, k))_{n,k∈N} is T P.

Note that a simple recursion relation for the numbers A(n, k) can be obtained by extracting the coefficient of x^{k} on both sides of (19). Also note that it is known (see, e.g., [15], ex. 3, p. 292) that every row of A is P F.

For r ∈ P and n, k ∈ N let S_{r}[n, k]_{q} be the r-associated q-Stirling number of the second kind defined in §5 of [13] (to which we refer the reader for its definition). It is known (see [13], Theorem 5.10) that the S_{r}[n, k]_{q}’s satisfy the following recursion relation

S_{r}[n, k]_{q} = [k]_{q^{r}} S_{r}[n − 1, k]_{q} + [\begin{matrix}n−1 \\ r−1 \end{matrix}]_{q} S_{r}[n − r, k − 1]_{q} ,

for all n, k ∈ P (where S_{r}[n, k]_{q} =^{def} 0 if either n < 0 or k < 0, and S_{r}[n, 0]_{q} = S_{r}[0, n]_{q} = δ_{0,n} for n ∈ N).

Conjecture 6.11 The matrix S_{r}(q) =^{def} (S_{r}[n, k]_{q})_{n,k∈N} is q − T P.

The developments described in section 5 are still very much in their infancy and thus open problems abound. For example, one can ask about the W -total positivity of any one of the totally positive functions discussed in [24], for other reflection groups W. Of all these functions, the only one which has been investigated so far is e^{xy}, for which the following is conjectured (see the comments following Example 6.4 in [21]).

Conjecture 6.12 The function K(x, y) = e^{xy} is W -totally positive for all finite reflection groups W.

The above conjecture has been proved if W is the Weyl group of a compact connected Lie group by K. I. Gross and D. St. P. Richards in [21] using deep results by Harish-Chandra (see [21], §4, and Theorem 6.1, for details). It does seem to be the case that W -total positivity is a much deeper concept then usual total positivity. However, we believe that the discovery of other W -totally positive functions will be mainly a matter of time.

References

[1] J. C. Ahuja and E. A. Enneking, Concavity property and a recurrence relation for associated Lah numbers, Fibonacci Quart., 17 (1979), 158-161.

[2] M. Aissen, I. J. Schoenberg, and A. M. Whitney, On the generating function of totally positive sequences, I, J. d’Anal. Math, 2 (1952), 93-103.

[3] T. Ando, Totally positive matrices, Linear Algebra Appl., 90 (1987), 165-219.

[4] F. Brenti, Query 389, Notices Amer. Math. Soc., 35 (1988), 315.

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

[6] F. Brenti, Log-concavity and combinatorial properties of Fibonacci Lattices, Europ. J. Combinatorics, 12 (1991), 459-476 .

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

[8] F. Brenti, Permutation enumeration, symmetric functions, and unimodality, Pacific J. Math., 157 (1993), 1-28.

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

[10] F. Brenti, G. F. Royle, and D. G. Wagner, Location of zeros of chromatic and related polynomials of graphs, Canadian J. Math., 46 (1994), 55-80.

[11] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, Europ. J. Combinatorics, 15 (1994), 417-441.

[12] F. Brenti, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry: an update, Contemporary Math., 178 (1994), to appear.

[13] F. Brenti, Combinatorics and total positivity, J. Combin. Theory Ser. A, 71 (1995), 175-218.

[14] L. Carlitz, Note on the numbers of Jordan and Ward, Duke Math. J. 38 (1971), 783-790.

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

[16] A. Edrei, On the generating function of totally positive sequences, II, J. d’Anal. Math, 2 (1952), 104-109.

[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] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math., 58 (1985), 300-321.

[19] I. Gessel and G. Viennot, Determinants, paths, and plane partitions, preprint.

[20] H. W. Gould, The q-Stirling numbers of the first and second kinds, Duke Math. J., 28 (1961), 281-289.

[21] K. I. Gross and D. St. P. Richards, Total positivity, finite reflection groups, and a formula of Harish-Chandra, J. Approximation Theory, to appear.

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

[23] S. Karlin and G. McGregor, Coincidence probabilities, Pacific J. Math., 9 (1959), 1141-1164.

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

[25] D. Knuth and J. Szwarcfiter, A structured program to generate all topological sorting arrangements, Inform. Process. Lett., 2 (1974), 153-157.

[26] A. Kalvin and Y. Varol, On the generation of all topological sortings, J. Algorithms, 4 (1983), 150-162.

[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. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc., 5 (1973), 85-90.

[29] G. Lusztig, Total positivity in reductive groups, in Lie Theory and Geometry 123 (J. L. Brylinski et al., editors), Birkhauser, Boston-Basel-Berlin, 1994, 531-568.

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

[31] J. Neggers, Representations of finite partially ordered sets, J. Combin. Inform. System Sci., 3 (1978), 113-133.

[32] R. C. Read and W. T. Tutte, Chromatic polynomials, in Selected Topics in Graph Theory 3 (Beineke and Wilson, editors), Academic Press, New York, 1988.

[33] V. Reiner, Quotients of Coxeter complexes and P-partitions, Memoirs Amer. Math. Soc., no. 460 (1992).

[34] V. Reiner, Signed permutations statistics, Europ. J. Combinatorics, 14 (1993), 553-67.

[35] V. Reiner, Signed permutation statistics and cycle type, Europ. J. Combinatorics, 14 (19B93), 569-79.

[36] B. E. Sagan, Log concave sequences of symmetric functions and analogs of the Yacobi-Trudi determinants, Trans. Amer. Math. Soc., 329 (1992), 795-812.

[37] B. E. Sagan, A maj statistic for set partitions, Europ. J. Combinatorics, 12 (1991), 69-79.

[38] B. E. Sagan, The Symmetric Group , Wadsworth and Brooks/Cole, Pacific Grove, CA, 1991.

[39] I. J. Schoenberg, Some analytical aspects of the problem of smoothing, Courant Anniversary Volume, New York, 1948.

[40] R. P. Stanley, Ordered structures and partitions, Memoirs Amer. Math. Soc., no. 119 (1972).

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

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

[43] R. P. Stanley, Graph colorings and related symmetric functions: ideas and applications, preprint.

[44] J. R. Stembridge, Non-intersecting paths, pfaffians and plane partitions, Adv. in Math., 83 (1990), 96-131.

[45] J. R. Stembridge, Immanants of totally positive matrices are nonnegative, Bull. London Math. Soc., 23 (1991), 422-428.

[46] J. R. Stembridge, personal communication, April 1991.

[47] J. R. Stembridge, Some conjectures for immanants, Canad. J. Math., 44 (1992), 1079-1099.

[48] J. R. Stembridge, A Maple package for posets, preprint.

[49] E. Thoma, Die unzerlegbaren, positiv-definiten Klassenfunktionen der abzählbar unendlichen symmetrischen Gruppe, Math. Zeit., 85 (1964), 40-61.

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

[51] D. G. Wagner, The partition polynomial of a finite set system, J. Combin. Theory Ser. A, 56 (1991), 138-159.

[52] D. G. Wagner, Enumerative combinatorics of partially ordered sets, and total positivity of Hadamard products, Ph.D. Thesis, Massachusetts Institute of Technology, 1989.

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

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

[55] D. G. 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.

[56] D. West, Generating linear extensions by adjacent transpositions, J. Combin. Theory Ser. B, 58 (1993), 58-64.

[57] T. Zaslavsky, Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Memoirs Amer. Math. Soc., no.154 (1975).

School of Mathematics Institute for Advanced Study Princeton, NJ, 08540 U.S.A.