Discrete Concavity and Zeros of Polynomials
2009 (English)In: Electronic Notes in Discrete Mathematics, ISSN 1571-0653, Vol. 34, 531-535 p.Article in journal (Refereed) Published
Murota et al. have recently developed a theory of discrete convex analysis as a framework to solve combinatorial optimization problems using ideas from continuous optimization. This theory concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over the field of Puiseux series) with prescribed non-vanishing properties. 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. Due to limited space a more coherent treatment and proofs will appear elsewhere.
Place, publisher, year, edition, pages
2009. Vol. 34, 531-535 p.
half-plane property, hive, Horn's conjecture, jump system, M-convex, matroid, Puiseux series, Tarski's principle
IdentifiersURN: urn:nbn:se:kth:diva-153590DOI: 10.1016/j.endm.2009.07.088ScopusID: 2-s2.0-67651174439OAI: oai:DiVA.org:kth-153590DiVA: diva2:753071
QC 201410072014-10-072014-10-062014-10-07Bibliographically approved