UC Berkeley

We investigate two main overarching topics in the theory of stable polynomials.

1. Differential and Difference Operators. We first study root properties of differen-

tial and difference operators. This includes the location of roots, the spacing between

roots, and the effect of linear operators on the roots. Our results in this direction

are mainly for the purpose of theory, with motivation being derived from previous

applications which rely on such results.

2. Applications to Graphs. We next study some examples of the connection between

graphs and polynomials. This includes a study of polynomial capacity and its relation

to bipartite matchings, as well as a study of the roots of the independence polynomial

and implications of various properties. Our results in this direction are applications of

the theory of stable polynomials, and demonstrates their use in combinatorics.

In the vein of (1), we extend the root bound of [47] to demonstrate the submodular nature

of the roots of real-rooted polynomials. This natural extension leads to further questions

on generalizations to multivariate polynomials, which are important steps on the path to

understanding the barrier arguments of Marcus-Spielman-Srivastava. We further settle a

conjecture of Brändén-Krasikov-Shapiro on a finite difference convolution which preserves

the spacing of roots of real-rooted polynomials. This convolution generalizes the one studied

by Marcus-Spielman-Srivastava, and the connections between these results yield interesting

open problems which have not yet been fully explored.

Towards (2), we combine the Borcea-Brändén characterization of stability preservers with

Gurvits’ capacity results to produce a theory of capacity preservers. We use this to give a new

proof of Csikvári’s lower bound on the matchings of a biregular bipartite graph. In another

direction, we give a new proof of the Chudnovsky-Seymour result on the real-rootedness of

the independence polynomial of a claw-free graph. We also prove root bounds similar to that

of Heilmann-Lieb for a class of independence polynomials, using an interesting multivariate

extension of Godsil’s divisibility relations for the matching polynomial.