×

The applications of total positivity to combinatorics, and conversely. (English) Zbl 0895.05001

Gasca, Mariano (ed.) et al., Total positivity and its applications. Meeting, Zaragoza in Jaca, Spain, September 26–30, 1994. Dordrecht: Kluwer Academic Publishers. Math. Appl., Dordr. 359, 451-473 (1996).
An infinite real matrix \(M=(M_{n,k})\) \((n, k\) non-negative integers) is totally positive (TP) if every minor of \(M\) has non-negative determinant. An infinite (real) sequence \(\{a_i\}\), \(i\geq 0\), is a Polya frequency (PF) sequence if \(A=(A_{n,k} =a_{n-k})\) (where \(a_i=0\) when \(i<0)\) is TP, which may also be written in generating function form when \(a_0=1\), that \(\sum a_iz^i= e^{az} \prod_{i\geq 0} (1+\alpha_iz)/ \prod_{i\geq 0} (1-\beta_iz)\), with \(\alpha_i \geq 0\), \(\beta_i\geq 0\), \(\sum \alpha_i+ \sum\beta_i< \infty\).
As the author of this survey chapter points out, the fact many combinatorial situations are described by generating functions of this “PF-type” indicates that TP-icity operating through PF-icity ought to be a very useful perspective on potential methods of attack on a variety of sticky combinatorial problems, some of which may be at least partially cracked when approached from this perspective. Questions of most interest in this area of interaction so far at least seem to be concerned with log-concavity or unimodality of sequences, which in the case of polynomials (i.e., finite sequences) specializes to the observation that roots be real. Many instances are pointed out, whence even if several be well known to a knowledgeable reader, others are seen to be interesting if not quite new. Furthermore, curious students of other aspects of TP-theory explained in other chapters may well find that not only is the flow of technique from TP-theory to combinatorics, but given the sophistication of available information as illustrated, progress in whatever their speciality may be achieved by taking advantage of what is available in combinatorics as ably illustrated in the survey reviewed.
For the entire collection see [Zbl 0884.00045].

MSC:

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
15-02 Research exposition (monographs, survey articles) pertaining to linear algebra
68-02 Research exposition (monographs, survey articles) pertaining to computer science
40-02 Research exposition (monographs, survey articles) pertaining to sequences, series, summability
60-02 Research exposition (monographs, survey articles) pertaining to probability theory
62-02 Research exposition (monographs, survey articles) pertaining to statistics

Software:

posets
PDFBibTeX XMLCite