Workshop

: Hyperbolic polynomials are generalizations of determinantal polynomials, and hyperbolicity cones are generalizations of the cone of positive semidefinite matrices. 

I will show how the recent Marcus-Spielman-Srivastava theorem (implying the Kadison-Singer conjecture) may be generalized to hyperbolic polynomials, and point to some potential applications in combinatorics. 

The generalized Lax conjecture asserts that hyperbolicity cones are linear sections of the cone of positive semidefinite matrices. Recently the speaker disproved an algebraic strengthening of this conjecture by using Ingleton's inequality for matroids that are representable over some field. Kinser recently introduced an infinite family of inequalities that generalize Ingleton's inequality. For each Kinser inequality we construct a Strong Rayleigh matroid which fails to satisfy the inequality. This produces an infinite family of hyperbolic polynomials such that no power of a polynomial in the family is a determinantal polynomial. 

The second part of this talk is based on joint work with Nima Amini.  

I will introduce the method of interlacing polynomials and analysis by barrier functions through a proof of the Restricted Inevitability Principle.  I will state Weaver's discrepancy-theoretic version of the Kadison-Singer Conjecture, and sketch the role that hyperbolic polynomials play in its proof.  If time permits, I will connect these with Ramanujan graphs and the matchings polynomials of graphs.

On the space of real symmetric matrices, the determinant is hyperbolic with respect to the cone of positive definite matrices. As a consequence, the determinant of a matrix of linear forms that is positive definite at some point is a hyperbolic polynomial.  A celebrated theorem of Helton and Vinnikov states that any hyperbolic polynomial in three variables has such a determinantal representation. In more variables, this is no longer the case.  During this talk, we will examine hyperbolic polynomials that do and do not have definite determinantal representations. Interlacing polynomials will play an interesting role in this story and form a convex cone in their own right.

A $k$-matching in a graph $X$ is a set of $k$ vertex-disjoint edges. If we denote

the number of $k$-matchings in a graph $G$ by $p(G,k)$ and $|V(G)|=n$, then its matching polynomial is

\[

\mu(G,t) = \sum_k (-1)^k p(G,k) t^{n-2k}.

\]

It is thus a form of generating function, with fudge factors inserted to make our work easier.

Matchings are a central topic in graph theory, but nonetheless this polynomial appeared in Physics and in Chemistry, before becoming an object of interest to graph theorists. If the graph $G$ is a forest, its matching polynomial coincides with the characteristic polynomial of the adjacency matrix of $G$, and considering the analogies between these two polynomials has proved very fruitful. In my talk I will present some of the history of the matching polynomial, along with interesting parts of its theory.

In this talk, I will examine the spectrum of random k-lifts of d-regular graphs. We show that, for random shift k-lifts (which includes 2-lifts), if all the nontrivial eigenvalues of the base graph G are at most \lambda in absolute value, then with high probability depending only on the number n of nodes of G (and not on k), if k is *small enough*, the absolute value of every nontrivial eigenvalue of the lift is at most O(\lambda).  While previous results on random lifts were asymptotically true with high probability in the degree of the lift k, our result is the first upperbound on spectra of lifts for bounded k. In particular, it implies that a typical small lift of a Ramanujan graph is almost Ramanujan. I will also discuss some impossibility results for large k, which, as one consequence, imply that there is no hope of constructing large Ramanujan graphs from abelian k-lifts. based on joint and ongoing work with Naman Agarwal  Karthik Chandrasekaran and Vivek Madan

Box spaces of finitely generated groups are disjoint union of Cayley graphs of finite quotients associated with some decreasing sequence of finite index normal subgroups of the given group. In 1973 Margulis gave the first explicit construction of expanders by proving that box spaces of property (T) groups are expanders. In 2012 Mendel and Naor showed the existence of two expanders $F_1,F_2$ such that $F_1$ does not coarsely embed into $F_2$. In February 2015, Hume constructed a continuum of expanders with unbounded girth, not coarsely embedding into one another. In joint work with Ana Khukhro, we construct countably many expanders with bounded girth, as box spaces of groups with property $(\tau)$, and prove that they do not coarsely embed into one another.

During the last two decades, hyperbolic polynomials have been influential in significant advances in diverse fields of mathematics.

In this talk, I will touch focus their role in optimization and convex analysis.

Given a k-edge-connected graph G=(V,E), a spanning tree T is a-thin w.r.t. G, if for any S⊂V, |T(S,V−S)|≤a.|E(S,V−S)|. The thin tree conjecture asserts that for a sufficiently large k (independent of size of G) every k-edge-connected graph has a 1/2-thin tree. This conjecture can be seen as an L1 analogous of KS_r, for r=k, restricted to graphs. It is intimately related to designing approximation algorithms for Asymmetric Traveling Salesman Problem (ATSP).

In this work, we show that any k-connected graph has a polyloglog(n)/k-thin spanning tree. This implies that the integrality gap of the natural LP relaxation of ATSP is at most polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n). This is the first significant improvement over the classical O~(log n) approximation factor for ATSP. Our proof builds on the method of interlacing polynomials of Marcus, Spielman and Srivastava and employs several tools from spectral graph theory and high dimensional geometry.

Based on a joint work with Nima Anari.

Let $X $ be a real subvariety of codimension $\ell$ in the complex projective space ${\mathbb P}^d$.
We say that $X$ is hyperbolic with respect to a real linear space $V$ of dimension $\ell-1$
if $X \cap V = \emptyset$ and $X$ intersects any real linear space of dimension $\ell$ through $V$
in real points only.
Alternatively, if $Y$ is the associated hypersurface of $X$ in the Grassmanian ${\mathbb G}(\ell-1,d)$
of $\ell-1$-dimensional linear spaces in ${! \mathbb P}^d$, then $V \not\in Y$ and $Y$ intersects any
real one-dimensional Schubert cycle through $V$ in real points only.

In the case $\ell=1$, i.e., $X$ is a hypersurface, this simply means that $X$ is the zero locus of a homogeneous
hyperbolic polynomial.

I will discuss hyperbolic subvarieties of a higher codimension, the analogues of hyperbolicity cones,
and a class of definite Hermitian determinantal representations that witnesses hyperbolicity.
It turns out that the analogue of the Lax conjecture holds --- any real curve in ${\mathbb P}^d$ that is hyperbolic
with respect to some $d-2$-dimensional linear space admits a definite Hermitian, or even real symmetric, determinantal representation.