MathLabs

解法:马库斯–斯皮尔曼–斯里瓦斯塔瓦利用交错族给出的证明(2013年)

第 5/8 步:交错族:保证存在一个具体的好结果,而不只是平均值好
通俗地说

把独立随机向量 wiw_i 的有限种选择想象成一棵树的叶子,逐一决定每个选择。在每个内部节点,多项式是子节点多项式按概率加权的平均。若子节点有公共交错,则至少有一个子节点的最大根不超过父节点的最大根。沿树重复这一过程,就能选出一个最大特征值受控的具体结果。

{pω}ω interlacing family  ⟹  ∃ ω0: λmax⁡(pω0)≤λmax⁡(Eωpω)\{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)
详细分析

以有根选择树的结果为下标的一组有限实根多项式 {pω}ω\{p_\omega\}_\omega,若每组兄弟节点都有公共交错且每个父节点是它们的加权和,就构成交错族。交错族 I 定理给出一个结果 ω0\omega_0,其最大根不超过加权平均的最大根。这里的结果是 wiw_i 的有限支集选择;最后的直和提升把选出的结果转换为两块划分。

本步骤中的术语
公共交错
两个次数相同的实根多项式,若存在一个实根多项式,其根与这两者的根都交替出现,则称二者有公共交错;这正是使平均值能够控制极值的精确组合条件。
本步骤用到的知识