Worked solution: Marcus–Spielman–Srivastava proof via interlacing families (2013)

Step 5 of 8: Interlacing families: guaranteeing one good outcome, not just a good average

In plain words

Imagine the finitely many choices of the independent random vectors $w_i$ as leaves of a tree, deciding one choice at a time. At each internal node, the polynomial is the probability-weighted average of its children's polynomials. If the children have a common interlacing, the largest root of at least one child is no larger than that of the parent. Repeating this down the tree selects one concrete outcome with a controlled largest eigenvalue.

\{p_\omega\}_\omega \text{ interlacing family} \implies \exists\, \omega_0:\ \lambda_{\max}(p_{\omega_0}) \le \lambda_{\max}\Big(\mathbb{E}_\omega p_\omega\Big)

Detailed analysis

A finite collection of real-rooted polynomials $\{p_\omega\}_\omega$ , indexed by outcomes of a rooted choice tree, forms an interlacing family when every sibling set has a common interlacing and each parent is their weighted sum. The Interlacing Families I theorem then gives an outcome $\omega_0$ whose largest root is at most the largest root of the weighted average. Here the outcomes are the finite-support choices of the $w_i$ ; the direct-sum lift at the end converts the selected outcomes into a two-block partition.

Terms in this step

Common interlacing: Two real-rooted polynomials of the same degree have a common interlacing if there is a single real-rooted polynomial whose roots alternate with the roots of each of the two; this is the precise combinatorial condition that lets averages control extremes.

Knowledge used in this step

Operator theory