DISCRETE CONCAVITY AND THE HALF-PLANE PROPERTY

作者：Branden Petter^*

来源：SIAM Journal on Discrete Mathematics, 2010, 24(3): 921-933.

DOI：10.1137/090758738

• M-convex
• jump system
• matroid
• half-plane property
• tropicalization
• Puiseux series
• Tarski's principle
• hive
• Horn's conjecture

Murota et al. have recently developed a theory of discrete convex analysis which concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over a field of generalized Puiseux series) with prescribed non-anishing properties. This family contains several of the most well studied M-concave functions in the literature. In the language of tropical geometry, we study the tropicalization of the space of polynomials with the half-plane property and show that it is strictly contained in the space of M-concave functions. We also provide a short proof of Speyer's "hive theorem" which he used to give a new proof of Horn's conjecture on eigenvalues of sums of Hermitian matrices.

• 出版日期2010