解法: 交差族によるMarcus–Spielman–Srivastavaの証明(2013年)
ざっくり言うと
独立なランダムベクトル の有限個の選択肢を、一度に一つずつ決める木の葉として考える。各内部節点の多項式は、子の多項式の確率加重平均である。子たちが共通交差を持てば、少なくとも一つの子の最大根は親の最大根以下になる。この操作を木の下まで繰り返すことで、最大固有値が制御された具体的な結果を一つ選べる。
詳しい解説
根付きの選択木の結果で添字付けられた実根多項式の有限集合 は、各兄弟集合が共通交差を持ち、各親がそれらの重み付き和であるとき交差族をなす。Interlacing Families I の定理により、重み付き平均の最大根以下の最大根を持つ結果 が得られる。ここで結果は の有限台の選択であり、最後の直和リフトが選ばれた結果を二つのブロックへの分割に変換する。
- 共通交差
- 同じ次数の二つの実根多項式が共通交差を持つとは、その両方の根と交互に現れる根を持つ単一の実根多項式が存在することをいう。これは平均が極値を制御することを可能にする正確な組合せ論的条件である。