The following 5 lectures were given by Shayan Oveis Gharan ↗ (University of Washington) on the ‘Prague Summer School on Discrete Mathematics 2020’.

Real stable polynomials and strongly Rayleigh distributions ↗

Notation

  • polynomial $p \in \mathbb{R} [Z_1,\dots,Z_n]$
  • $p \in \mathbb{R}_{\ge 0}$ non-negative coefficients
  • $p \in \mathbb{R} [Z_1,\dots,Z_n]$ is $d$-homogenous if (every monimial of p has degree d)
  • $\mathcal{H}$ is set of points in complex plain s.t. imaginary value is positive.
  • $p \in \mathbb{R}$ is real stable if $p(Z_1,\dots,Z_n) \ne 0$ whenever $(Z_1,\dots,Z_n)\in\mathcal{H}^n$.
  • $z^s = \Pi_{i\in S}z_i$

Intuition

Fact: If $p\in \mathbb{R}[Z]$ is real rooted iff $p$ is real stable.

Equivalent definition: $p \in \mathbb{R}[Z_1,\dots,Z_n]$ is real stable iff for all $a\in \mathbb{R}^n_{>0}$ and $b\in\mathbb{R}^n$ the univariable polynom $p(at+b)=f(t)$ not identically zero and is real rooted.

Example: Roots of $1-z_1z_2$ ↗ are hyperbolae-like and is real stable. Because all ‘positive’ lines (going from 3rd quadrant to 1st) are crossing both lines of the solutions, so they all cross $2$ solutions.

Roots of $1+z_1z_2$ ↗ is not real stable because there are lines which have different number of solutions (some cross no solution).

$p$ is real satble $\Rightarrow$ $p(at+b)$ is real rooted: By contradiction $\exists t:Im(t)\ne 0, p(at+b)=0$. We can assume $Im(t) > 0$ and define $z_i=a_it+b_i \forall i$ and see that $Im(t) > 0 \Rightarrow Im(Z_i) > 0 \forall i$. $p(Z_1,\dots,Z_n) = p(at+b)=0$, a contradiction.

$p(at+b)$ is not identically zero $\Rightarrow$ $p$ is real stable and real rooted. By contradiction if p is not real stabel $\Rightarrow$ $\exists z_1,\dots,z_n \in \mathcal{H}^n$ s.t. $p(z_1,\dots,z_n)=0$. Let $a_i = Im(z_i), b_i=Re(z_i) \Rightarrow a\in \mathbb{R}^n_{>0}, b\in\mathbb{R}^n$.

todo, few examples missing

Non-exampele $z_1^2+z_2^2$.

Mother of all stable polynomials

Thm: Given PSD matrices $A_1,\dots,A_n \in \mathbb{R}^{d\times d}$ and a symmetric matrix $B \in \mathbb{R}^{d\times d}$ then ${\rm det}(B+\sum Z_iA_i) = p(Z_1,\dots,Z_n)$.

Application: Matrix tree thm: $b_e=(u,v)=1u-1v$, $\frac{1}{n^2}{\rm det}(1^T + \sum z_eb_eb_e^T)=\sum_{T st}\Pi_{e\in T} z_e$ (generating polynomial of all spanning trees).

Thm (Choe-Oxly-Sokal-Wagner ‘02): The support of any multi-affine homogenous real stable polynomial corresponds to Bases of a matroid. Def: $p\in \mathbb{R}[Z_1,\dots,Z_n]$ is multi affine if every monomial is square free (doesn’t contain e.g. $z_2^2z_1$ or $z_5^3$).

Limitations

We cannot realize everything, we can realize only some Matroids.

Closure properties

Family of real state polynomials are closed under many operations.

$p,q\in\mathbb{R}[Z_1,\dots,Z_n]$ is real stable. Real state polynomials are closed under the following operations (e.g.):

  • $p \cdot q$ is real stable
  • (symmetrization) $r(Z_1,Z_3,\dots,Z_n)=p(Z_1,Z_1,Z_3,\dots,Z_n)$
  • (external field) $\lambda_1,\dots,\lambda_n > 0$, $r(Z_1,\dots,Z_n)=p(\lambda_1Z_1,\dots,\lambda_nZ_n)$
  • (specialization) $r(Z_2,\dots,Z_n) = p(a,Z_2,\dots,Z_n)$ for $Im(a) \ge 0$ (in particular if $a \in \mathbb{R}$)

(Limit of real stable polynomials is real stable.)

Some other closed operations:

  • (differentiation) $\frac{\partial P}{\partial z_i}$
  • (inversion) …

Strongly Reyleigh Distribution

(probabilistic analog of real stable polynomials)

Def: $\mu : 2^{[n]} \rightarrow \mathbb{R}{\ge 0}$ generating polynomial of $\mu$. $g\mu(z_1,\dots,z_n)=\mathbb{E}[z^s] = \sum_{S\subseteq[n]}\mu(S)z^S.

E.g. Two independent Bernoulli: $B_1,B_2$ TODO … cca 50m in the video, didn’t get it

Def $\mu$ is SR if $g_\mu$ is real stable.

Operations

  • Conditioning i in $g_\mu |i = z_i \partial{z_i}g_\mu / P[i]$ (note $/P[i]$ can be omitted because scaling doesn’t change roots).
  • Conditioning i out $g_\mu |{\bar i} = g\mu |_{z_i=0}$
  • projection Fix $T \subseteq [n]$. $\mu|T(a)=\sum{S:S\cap T=A}\mu(S)$, $A\subseteq T$; projction is exactly $g_\mu |_{z_i=1} \forall i\not\in T$.
  • external field $\mu: \lambda_1,\dots,\lambda_n > 0$, $\mu \cdot \lambda(S) = \mu(S) \cdot \lambda^S$

App: $G=(V,E)$, $\mu$ = uniform distribution over spanning trees, $g_\mu = 1/{\text{#st}} \sum_T z^T$ real stabel, $\mu$ is S.R.

Lemma: Say $F\subseteq E$ define $a_i=\mathbb{P}[|T\cap F|=i]$, $\Pi_i a_i$ correspond to sum of independent Bernoullis.

Pf: $g_\mu$ first project onto $F$. $g_1 = g_\mu|{z_e=1,\forall e\not\in F}$. $g_2 = g_1(t,t,t,\dots,t)$ (symmetrization), $g_2$ must be real rooted. $g_2 = a_0 + a_1t + \dots + a{|F|}t^{|F|}$. Bacground notes: $\exists$ independent Bernoullis.

We can study: What is the probability $\mathbb{P}[|T\cap F| \text{ is odd}]$? (used in TSP)