THE COMBINATORICS OF MIXED VOLUMES

Mixed volumes were discovered close to the turn of the century (19th to 20th) by H. Minkowski. They generalize the usual Euclidean n-volume by instead associating a nonnegative real number to an n-tuple of convex bodies in n-space.

Mixed volumes are of considerable interest within convex geometry, having appeared in various famous inequalities such as the one by Alexandrov and Fenchel. However, it was discovered in the mid-1970's by Kouchnirenko that polytope volumes actually relate to the number of roots of certain polynomial systems! A. Khovanskii did some important foundational work regarding this connection, and then D. N. Bernshtein wrote the first general statement of the fact that the number of complex roots (with all coordinates nonzero) of a polynomial system is precisely the mixed volume of a particular n-tuple of polytopes (on average).

Returning to combinatorics however, an interesting fundamental question is when one mixed volume is bigger than another. More precisely, if P_1,Q_1,...,P_n,Q_n are polytopes in n-space, and P_i is contained in Q_i for all i, under what conditions are the mixed volumes M(P_1,...,P_n) and M(Q_1,...,Q_n) identical?

This question is answered (for the case of rational polytopes) in ``A Convex Geometric Approach to Counting the Roots of a Polynomial System'' (Theoretical Computer Science, vol. 133 (1), pp. 105-140, October, 1994). Section 2.5 is most relevant to convex geometers, and the remainder of the paper covers extensions of the connection to polynomial systems. An on-line errata sheet has just been completed, and is available in DVI format or Postscript format.

Another interesting application of mixed volumes occurs in deriving complexity bounds for certain algorithms in algebraic geometry. For instance, the complexity estimates for a recent algorithm of mine for real and complex root counting rely on certain identities for mixed volumes of Minkowski sums. This is covered (admittedly, rather tangentially) in ``Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting''. I hope to write a version more specifically directed to convex geometers soon.