## 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.