Nima Amini: Hyperbolic polynomials and matroids

Abstract

Hyperbolic polynomials are multivariable generalizations of univariate real-rooted polynomials. Despite their origins in PDE-theory, these polynomials have recently made appearances in several different areas, including optimization, real algebraic geometry and combinatorics. Notably in 2013 they were used by Marcus, Spielman and Srivastava to give a proof of the longstanding Kadison-Singer conjecture from 1959. From a combinatorial point of view, hyperbolic polynomials give rise to (hyperbolic) matroids and vice versa. This connection has provided important instances for testing a famous conjecture called the Generalized Lax Conjecture (GLC). The conjecture states that all the cones associated to hyperbolic polynomials are linear slices of the cone of positive semidefinite matrices, in other words, "hyperbolic programming is the same as semidefinite programming". A stronger version of this conjecture was disproved using the only known instance of a non-linear hyperbolic matroid, namely the Vámos matroid. In recent work (with P.Brändén) we have constructively proved the existence of an infinite number of such matroids, in particular affirming a conjecture by Vinzant et al. The work has also led to newfound consequences for the GLC. The talk will center around GLC and give an overview of the connection between hyperbolic polynomials and matroids.