Title: Daniel's Flashcards / Year 4 / Term 3 / Spectral Graph Theory

html: Definition 1.1 (Hermitian). M is Hermitian if M = M H, where M H ( x , y ) = M ( y , x ) ¯.
If M is Hermitian, then ⟨ M f , g ⟩ = ⟨ f , M g ⟩.
nothing: True

html: Theorem 1.2 (Spectral theorem for Hermitian matrices). Assuming that:
- Ω finite
- M : Ω × Ω → ℂ Hermitian
- | Ω | = n
Then there exist λ 1 , … , λ n ∈ ℝ and φ 1 , … , φ ) n ∈ l 2 ( Ω ) non-zero such that
- (1)
M φ i = λ i φ i
- (2)
𝟙 ⟨ φ i , φ j ⟩ 𝟙 i = j
- (3)
M = ∑ ⁡ i = 1 n λ φ i φ i H
- (4)
there exists U orthogonal such that U M U H = diag ⁡ ( λ i )
- (5)
if M is real, then can take φ to be real (φ : Ω → ℝ)
proof: Proof. Want M f = z f for some z ∈ ℂ. So want ( z I − M ) f = 0 to have a non-trivial solution f ≠ 0. This happens if and only if z I − M is singular, which happens if and only if det ⁡ ( z I − M ) = 0.
z ↦ det ⁡ ( z I − M ) is a degree n polynomial in ℂ (degree n since the leading term is z n), so the fundamental theorem of algebra shows that there exists λ ∈ ℂ such that det ⁡ ( λ I − M ) = 0. □
nothing: True

html: Lemma 1.3. Any M has an eigenpair ( λ , φ ).
proof: Proof. Want M f = z f for some z ∈ ℂ. So want ( z I − M ) f = 0 to have a non-trivial solution f ≠ 0. This happens if and only if z I − M is singular, which happens if and only if det ⁡ ( z I − M ) = 0.
z ↦ det ⁡ ( z I − M ) is a degree n polynomial in ℂ (degree n since the leading term is z n), so the fundamental theorem of algebra shows that there exists λ ∈ ℂ such that det ⁡ ( λ I − M ) = 0. □

html: Lemma 1.4. Assuming that:
- M is Hermitian
Then all eigenvalues are real
proof: Proof.
λ ¯ ⟨ φ , φ ⟩ = ⟨ λ φ , φ ⟩ = ⟨ M φ , φ ⟩ = ⟨ φ , M φ ⟩ = ⟨ φ , λ φ ⟩ = λ ⟨ φ , φ ⟩
Since φ ≠ 0, ⟨ φ , φ ⟩ = ∥ φ ∥ 2 > 0, hence λ = λ ¯, i.e. λ ∈ ℝ. □
cloze1: True

html: Lemma 1.5. Assuming that:
- M Hermitian
- λ i ≠ λ j are eigenvalues of M with eigenvectors φ i, φ j
Then ⟨ φ i , φ j ⟩ = 0.
proof: Proof.
λ i ⟨ φ i , φ j ⟩ = ⟨ M φ i , φ j ⟩ = ⟨ φ i , M φ j ⟩ = λ j ⟨ φ i , φ j ⟩
Since we assumed λ i ≠ λ j, this gives ⟨ φ i , φ j ⟩ = 0. □
cloze1: True

html: Definition 1.8 (Rayleigh quotient). ⟨ f , M f ⟩ ⟨ f , f ⟩ is called the Rayleigh quotient.
nothing: True

html: λ 1 ( M ) = min ⁡ f ≠ 0 q M ( f ) and it is attained only on
Lemma 1.10. eigenfunctions of λ 1.
proof: Proof. Let f = ∑ ⁡ i α i φ i and M f = ∑ ⁡ i α i λ i φ i. Then
Q M ( f ) = ⟨ f , M f ⟩ ∑ i , j α i α j λ i ⟨ φ i , φ j ⟩ = ∑ i α i 2 λ i
and
q M ( f ) = ∑ i α i 2 λ i ∑ i α i 2 ≥ λ i .
Equality occurs here if and only if ∑ ⁡ i ( λ 1 − λ i ) α i 2 = 0. So α i = 0 whenever λ i > λ 1. □

html: Assuming:
Lemma 1.11. - φ 1 is an eigenfunction of λ 1. Then: λ 2 ( M ) = min ⁡ f ⊥ φ 1 f ≠ 0 q M ( f ), and it is attained only on eigenfunctions of λ 2 ( M ).
proof: Proof.
q M ( f ) = ∑ i α i 2 λ i ∑ i α i 2 ≥ α 1 2 λ 1 + ( ∑ i ≥ 2 α i 2 ) λ 2 ∑ i α i 2 .
So
min ⁡ f ⊥ φ i f ≠ 0 q M ( f ) ≥ λ 2 .
Deal with the equality case similarly to before. □

html: Definition 2.1 (Adjacency matrix). The adjacency matrix of a graph G is the matrix A G : V × V → ℝ defined by
A G ( x , y ) = { 1 { x , y } ∈ E ( G ) 0 { x , y } ∉ E ( G )
nothing: True

html: Definition 2.2 (Degree matrix). The degree matrix of a graph G is the matrix D G : V × V → ℝ defined by
D G ( x , y ) = { deg ⁡ ( x ) x = y 0 otherwise
nothing: True

html: Definition 2.3 (Laplacian matrix). The Laplacian matrix of a graph G is defined by L G = D − A.
nothing: True

html: Corollary 2.4. For any graph G, L G is a positive semi definite matrix with eigenvector 1, which has eigenvalue 1.
proof: Proof. Since Q L ( f ) = ∑ ⁡ x ∼ y ( f ( x ) − f ( y ) ) 2, we see that Q L ( f ) ≥ 0, with equality when f is constant. □
cloze1: True

html: Proposition 2.5. λ 2 ( L g ) > 0 if and only if G is connected. λ k ( L G ) = 0 if and only if G has at least k connected components.
proof: Proof.
λ 2 = min ⁡ f ⊥ 1 f ≠ 0 ∑ x ∼ y ( f ( x ) − f ( y ) ) 2 ⟨ f , f ⟩ ≥ 0
Equality happens if and only if Q L ( f ) = 0, which happens if and only if f is constant on connected components. The dimension of { f : constant on connected components } is the number of connected components of G.
TODO? □
cloze1: True

html: Definition 3.1 (Expansion). Given a d-regular graph G and S ⊆ V, the expansion of S is
Φ ( S ) : = e ( S , V ∖ S ) d | S | .
nothing: True

html: Definition 3.2 (Edge expansion). The (edge) expansion of a cut ( S , V ∖ S ) is defined as
Φ ( S , V ∖ S ) : = max ⁡ { Φ ( S ) , Φ ( V ∖ S ) } = e ( S , V ∖ S ) d min ⁡ { | S | , | V ∖ | } .
nothing: True

html: Definition 3.3 (Edge expansion of a graph). The edge expansion of a graph is
Φ ( G ) : = min ⁡ S ⊆ V ∅ ≠ S ≠ V Φ ( S , V ∖ S ) = min ⁡ S ⊆ V 0 < | S | < | V | ∕ 2 Φ ( S ) .
nothing: True

html: Theorem 3.4 (Cheeger’s inequality). Assuming that:
- G be d-regular
Then
λ 2 ( L ~ G ) 2 ≤ Φ ( G ) ≤ 2 λ 2 ( L ~ G ) .
proof: Proof. Let λ i, φ i such that f = ∑ ⁡ i λ i φ i and g = ∑ ⁡ i β i φ i. Then
q M ( f + g ) = ∑ i λ i ( α i + β i ) 2 ∥ f + g ∥ 2 ≤ ∑ i λ i ( 2 α i 2 + 2 β i 2 ) ∥ f ∥ 2 + ∥ g ∥ 2 .
Then
q M ( f + g ) ≤ 2 ( ∑ i λ i α i 2 + ∑ i λ i β i 2 ∥ f ∥ 2 + ∥ g ∥ 2 ) = 2 ( q M ( f ) ∥ f ∥ 2 + q M ( g ) ∥ g ∥ 2 ∥ f ∥ 2 + ∥ g ∥ 2 ) ≤ 2 max ⁡ { q M ( f ) , q M ( g ) } □
nothing: True

html: Lemma 3.5. Assuming that:
- M is symmetric positive semi-definite
- ⟨ f , g ⟩ = 0
Then
q M ( f + g ) ≤ 2 max ⁡ { q M ( f ) , q M ( g ) } .
proof: Proof. Let λ i, φ i such that f = ∑ ⁡ i λ i φ i and g = ∑ ⁡ i β i φ i. Then
q M ( f + g ) = ∑ i λ i ( α i + β i ) 2 ∥ f + g ∥ 2 ≤ ∑ i λ i ( 2 α i 2 + 2 β i 2 ) ∥ f ∥ 2 + ∥ g ∥ 2 .
Then
q M ( f + g ) ≤ 2 ( ∑ i λ i α i 2 + ∑ i λ i β i 2 ∥ f ∥ 2 + ∥ g ∥ 2 ) = 2 ( q M ( f ) ∥ f ∥ 2 + q M ( g ) ∥ g ∥ 2 ∥ f ∥ 2 + ∥ g ∥ 2 ) ≤ 2 max ⁡ { q M ( f ) , q M ( g ) } □
cloze1: True

html: Lemma 3.6. Assuming that:
- ψ : V → ℝ
- ⟨ ψ , 1 ⟩ = 0
- let ( S , V ∖ S ) = Fiedler ⁡ ( G , ψ )
Then
Φ ( S , V ∖ S ) ≤ 2 q L ~ G ( ψ ) .
proof: Proof of Lemma 3.7 . If ⟨ φ , 1 ⟩ = 0 then
q L ~ G ( φ + α 1 ) = Q L ~ G ( φ + α 1 ) ∥ φ + α 1 ∥ 2 = Q L ~ G ( φ ) ∥ φ ∥ 2 + α 2 ≤ Q L ~ G ( φ ) ∥ φ ∥ 2 = q L ~ G ( φ )
Let m ∈ ℝ be the median of φ.
| { x ∈ V : φ ( x ) > m } | ≤ | V | 2 | { x ∈ V : φ ( x ) < m } | ≤ | V | 2
φ ¯ = φ − m 1, q L ~ G ( φ ¯ ) ≤ q L ~ G ( φ ). Let φ ¯ = φ ¯ + − φ ¯ −, where φ ¯ + , φ ¯ − : V → ℝ ≥ 0. So
φ ¯ ( x ) = { φ ¯ + ( x ) φ ( x ) > m − φ ¯ − ( x ) φ ( x ) < m 0 φ ( x ) = m .
Note ⟨ φ ¯ − , φ ¯ + ⟩ = 0.
Claim: either φ ¯ + or φ ¯ − suffices.
q L ~ G ( φ ) ≥ q L ~ G ( φ ¯ ) = q L ~ G ( φ ¯ + − φ ¯ − ) = ∑ x ∼ y ( φ ¯ + ( x ) − φ ¯ − ( x ) − φ ¯ + ( y ) + φ ¯ − ( y ) ) 2 ∥ φ ¯ + − φ ¯ − ∥ 2 = ∑ x ∼ y ( ( φ ¯ + ( x ) − φ ¯ + ( y ) ) − ( φ ¯ − ( x ) − φ ¯ − ( x ) ) 2 ∥ φ ¯ + ∥ 2 + ∥ φ ¯ − ∥ 2 ≥ ∑ x ∼ y ( φ ¯ + ( x ) − φ ¯ + ( y ) ) 2 + ( φ ¯ − ( x ) − φ ¯ − ( y ) ) 2 ∥ φ ¯ + ∥ 2 + ∥ φ ¯ − ∥ 2 = q L ~ G ( φ ¯ + ) ∥ φ ¯ ∥ 2 + q L ~ G ( φ ¯ − ) ∥ φ ¯ − ∥ 2 ∥ φ ¯ ∥ 2 + ∥ φ ¯ − ∥ 2 □
cloze1: True

html: Lemma 3.7. Assuming that:
- φ : V → ℝ
- ⟨ φ , 1 ⟩ = 0
Then there is ψ : V → ℝ ≥ 0 such that q L ~ G ( ψ ) ≤ q L ~ G ( ψ ), | supp ⁡ ψ | = | { x : ψ ( x ) > 0 } | ≤ | V | Q and any threshold cut for ψ is a threshold cut for φ.
proof: Proof of Lemma 3.7 . If ⟨ φ , 1 ⟩ = 0 then
q L ~ G ( φ + α 1 ) = Q L ~ G ( φ + α 1 ) ∥ φ + α 1 ∥ 2 = Q L ~ G ( φ ) ∥ φ ∥ 2 + α 2 ≤ Q L ~ G ( φ ) ∥ φ ∥ 2 = q L ~ G ( φ )
Let m ∈ ℝ be the median of φ.
| { x ∈ V : φ ( x ) > m } | ≤ | V | 2 | { x ∈ V : φ ( x ) < m } | ≤ | V | 2
φ ¯ = φ − m 1, q L ~ G ( φ ¯ ) ≤ q L ~ G ( φ ). Let φ ¯ = φ ¯ + − φ ¯ −, where φ ¯ + , φ ¯ − : V → ℝ ≥ 0. So
φ ¯ ( x ) = { φ ¯ + ( x ) φ ( x ) > m − φ ¯ − ( x ) φ ( x ) < m 0 φ ( x ) = m .
Note ⟨ φ ¯ − , φ ¯ + ⟩ = 0.
Claim: either φ ¯ + or φ ¯ − suffices.
q L ~ G ( φ ) ≥ q L ~ G ( φ ¯ ) = q L ~ G ( φ ¯ + − φ ¯ − ) = ∑ x ∼ y ( φ ¯ + ( x ) − φ ¯ − ( x ) − φ ¯ + ( y ) + φ ¯ − ( y ) ) 2 ∥ φ ¯ + − φ ¯ − ∥ 2 = ∑ x ∼ y ( ( φ ¯ + ( x ) − φ ¯ + ( y ) ) − ( φ ¯ − ( x ) − φ ¯ − ( x ) ) 2 ∥ φ ¯ + ∥ 2 + ∥ φ ¯ − ∥ 2 ≥ ∑ x ∼ y ( φ ¯ + ( x ) − φ ¯ + ( y ) ) 2 + ( φ ¯ − ( x ) − φ ¯ − ( y ) ) 2 ∥ φ ¯ + ∥ 2 + ∥ φ ¯ − ∥ 2 = q L ~ G ( φ ¯ + ) ∥ φ ¯ ∥ 2 + q L ~ G ( φ ¯ − ) ∥ φ ¯ − ∥ 2 ∥ φ ¯ ∥ 2 + ∥ φ ¯ − ∥ 2 □
cloze1: True

html: Lemma 3.8. Assuming that:
- ψ : V → ℝ ≥ 0
Then there is 0 < t ≤ ∥ ψ ∥ ∞ such that
Φ ( { x : ψ ( x ) ≥ t } ) ≤ 2 q L ~ G ( ψ ) .
proof: Proof of Lemma 3.7 . If ⟨ φ , 1 ⟩ = 0 then
q L ~ G ( φ + α 1 ) = Q L ~ G ( φ + α 1 ) ∥ φ + α 1 ∥ 2 = Q L ~ G ( φ ) ∥ φ ∥ 2 + α 2 ≤ Q L ~ G ( φ ) ∥ φ ∥ 2 = q L ~ G ( φ )
Let m ∈ ℝ be the median of φ.
| { x ∈ V : φ ( x ) > m } | ≤ | V | 2 | { x ∈ V : φ ( x ) < m } | ≤ | V | 2
φ ¯ = φ − m 1, q L ~ G ( φ ¯ ) ≤ q L ~ G ( φ ). Let φ ¯ = φ ¯ + − φ ¯ −, where φ ¯ + , φ ¯ − : V → ℝ ≥ 0. So
φ ¯ ( x ) = { φ ¯ + ( x ) φ ( x ) > m − φ ¯ − ( x ) φ ( x ) < m 0 φ ( x ) = m .
Note ⟨ φ ¯ − , φ ¯ + ⟩ = 0.
Claim: either φ ¯ + or φ ¯ − suffices.
q L ~ G ( φ ) ≥ q L ~ G ( φ ¯ ) = q L ~ G ( φ ¯ + − φ ¯ − ) = ∑ x ∼ y ( φ ¯ + ( x ) − φ ¯ − ( x ) − φ ¯ + ( y ) + φ ¯ − ( y ) ) 2 ∥ φ ¯ + − φ ¯ − ∥ 2 = ∑ x ∼ y ( ( φ ¯ + ( x ) − φ ¯ + ( y ) ) − ( φ ¯ − ( x ) − φ ¯ − ( x ) ) 2 ∥ φ ¯ + ∥ 2 + ∥ φ ¯ − ∥ 2 ≥ ∑ x ∼ y ( φ ¯ + ( x ) − φ ¯ + ( y ) ) 2 + ( φ ¯ − ( x ) − φ ¯ − ( y ) ) 2 ∥ φ ¯ + ∥ 2 + ∥ φ ¯ − ∥ 2 = q L ~ G ( φ ¯ + ) ∥ φ ¯ ∥ 2 + q L ~ G ( φ ¯ − ) ∥ φ ¯ − ∥ 2 ∥ φ ¯ ∥ 2 + ∥ φ ¯ − ∥ 2 □
cloze1: True

html: Definition 4.1 (Loewner order). For A, B matrices, write A ≼ B if B − A is positive semidefinite. In particular, A ≽ 0 if and only if A is positive semidefinite.
nothing: True

html: Definition 4.2 (eps-approximation). G is an 𝜀-approximation of H if
( 1 − 𝜀 ) L H ≼ L G ≼ ( 1 + 𝜀 ) L H .
nothing: True

html: Lemma 4.3. Given the definition ∥ M ∥ = max ⁡ f ≠ 0 ∥ M f ∥ ∥ f ∥ (for M symmetric), we have ∥ M ∥ = max ⁡ { | λ k ( M ) | }.
proof: Proof. f = ∑ ⁡ i α i φ i, M φ i = λ i φ i, ∥ f ∥ 2 = ∑ ⁡ i α i 2,
∥ M f ∥ 2 = ∥ ∑ i α i λ i φ i ∥ 2 = ∑ i α i 2 λ i 2 .
∥ M f ∥ ∥ f ∥ = ∑ i α i 2 λ i 2 ∑ i α i 2 ≤ max ⁡ k | λ k | . □
cloze1: True

html: Definition ((d,eps)-expander). G = ( V , E ), | V | = n is a ( d , 𝜀 )-expander if G is an 𝜀-approximation of d n K n.
nothing: True

html: Lemma 4.5 (Expander Mixing Lemma). Assuming that:
- G is d-regular
- G is a ( d , 𝜀 )-expander
Then ∀ ⁡ S , T ⊆ V,
| e ( S , T ) − d n | S | | T | | ≤ 𝜀 d n | S | | T | | S c | | T c | .
proof: Proof. 𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , L G 𝟙 T ⟩ = ⟨ 𝟙 S , ( d I − A G ) 𝟙 T ⟩, 𝟙 𝟙 ⟨ 𝟙 S , d I 𝟙 T ⟩ = d | S ∩ T |.
𝟙 𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , A G 𝟙 T ⟩ = ∑ x ∑ y 𝟙 S ( x ) A G ( x , y ) 𝟙 T ( y ) = ∑ x ∑ y 𝟙 x y ∈ E = e ( S , T )
d n L K n = d I − d n J.
𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , d n J 𝟙 T ⟩ = d n ⟨ 𝟙 S , J 𝟙 T ⟩ = d n ∑ x ∑ y J ( x , y ) = d n | S | | T | .
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 | e ( S , T ) − d n | S | | T | | = | ⟨ 𝟙 S , ( d n L K n − L G ) 𝟙 T ⟩ | ≤ ∥ 𝟙 S ∥ ∥ ( d n L K n − L G ) 𝟙 T ∥ ≤ ∥ 𝟙 S ∥ ∥ ( d n L K n − L G ) ∥ ∥ 𝟙 T ∥ ≤ λ ∥ 𝟙 S ∥ ∥ 𝟙 T ∥ = λ | S | | T | To get the better bound, we should consider functions which are perpendicular to 1: balanced function 𝟙 f S = 𝟙 S − | S | n 1.
𝟙 𝟙 L G f S = L G ( 𝟙 S − α ) = L 𝟙 S.
| e ( S , T ) − d n | S | | T | | = | ⟨ f S , ( d n L K n − L G ) f T ⟩ | ≤ λ ∥ f S ∥ ∥ f T ∥
∥ f S ∥ 2 = | S | ( 1 − | S | n ) 2 + ( n − | S | ) ( − | S | n ) 2 = | S | ( 1 − 2 | S | n + | S | 2 n 2 ) + ( n − | S | ) | S | 2 n 2 = | S | − 2 | S | 2 n + | S | 3 n 2 + | S | 2 n − | S | 3 n 2 = | S | − | S | 2 n = n | S | − | S | 2 n = | S | | S c | n So
| e ( S , T ) − d n | S | | T | | ≤ | S | | S c | | T | | T c | . □
nothing: True

html: Proposition 4.6. Assuming that:
- G a d-regular graph on n vertices
- λ , 𝜀 > 0, 𝜀 d = λ
Then the following are equivalent:
- (i) G is a ( n , d , λ )-graph
- (ii) λ k ( A G ) ∋ [ − λ , λ ], for 1 ≤ k ≤ n − 1
- (iii) λ k ( L G ) ∈ [ d − λ , d + λ ] for 2 ≤ k ≤ n
- (iv) λ k ( L ~ G ) ∈ [ 1 − λ d , 1 + λ d ] = [ 1 − 𝜀 , 1 + 𝜀 ] for 1 ≤ k ≤ n
- (v) ( 1 − 𝜀 ) d n L K n ≼ L G ≼ ( 1 + 𝜀 ) d n L K n
- (vi) G is ( d , 𝜀 )-expander (also ( d , λ d )-expander)
- (vii) ∥ L G − d n L K n ∥ ≤ 𝜀 d = λ
- (viii) ∥ A G − d n J ∥ ≤ 𝜀 d = λ
proof: Proof. 𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , L G 𝟙 T ⟩ = ⟨ 𝟙 S , ( d I − A G ) 𝟙 T ⟩, 𝟙 𝟙 ⟨ 𝟙 S , d I 𝟙 T ⟩ = d | S ∩ T |.
𝟙 𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , A G 𝟙 T ⟩ = ∑ x ∑ y 𝟙 S ( x ) A G ( x , y ) 𝟙 T ( y ) = ∑ x ∑ y 𝟙 x y ∈ E = e ( S , T )
d n L K n = d I − d n J.
𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , d n J 𝟙 T ⟩ = d n ⟨ 𝟙 S , J 𝟙 T ⟩ = d n ∑ x ∑ y J ( x , y ) = d n | S | | T | .
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 | e ( S , T ) − d n | S | | T | | = | ⟨ 𝟙 S , ( d n L K n − L G ) 𝟙 T ⟩ | ≤ ∥ 𝟙 S ∥ ∥ ( d n L K n − L G ) 𝟙 T ∥ ≤ ∥ 𝟙 S ∥ ∥ ( d n L K n − L G ) ∥ ∥ 𝟙 T ∥ ≤ λ ∥ 𝟙 S ∥ ∥ 𝟙 T ∥ = λ | S | | T | To get the better bound, we should consider functions which are perpendicular to 1: balanced function 𝟙 f S = 𝟙 S − | S | n 1.
𝟙 𝟙 L G f S = L G ( 𝟙 S − α ) = L 𝟙 S.
| e ( S , T ) − d n | S | | T | | = | ⟨ f S , ( d n L K n − L G ) f T ⟩ | ≤ λ ∥ f S ∥ ∥ f T ∥
∥ f S ∥ 2 = | S | ( 1 − | S | n ) 2 + ( n − | S | ) ( − | S | n ) 2 = | S | ( 1 − 2 | S | n + | S | 2 n 2 ) + ( n − | S | ) | S | 2 n 2 = | S | − 2 | S | 2 n + | S | 3 n 2 + | S | 2 n − | S | 3 n 2 = | S | − | S | 2 n = n | S | − | S | 2 n = | S | | S c | n So
| e ( S , T ) − d n | S | | T | | ≤ | S | | S c | | T | | T c | . □
cloze1: True

html: Lemma 4.7 (Expander Mixing Lemma). Assuming that:
- G = ( V , E ) an ( n , d , λ )-graph
- S , T ⊆ V (and define 𝟙 e ( S , T ) = ∑ ⁡ x ∈ S ∑ y ∈ T 𝟙 x y ∈ E)
Then | e ( S , T ) − d n | S | | T | | ≤ λ n | S | | S c | | T | | T c | ≤ λ | S | | T |
proof: Proof. 𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , L G 𝟙 T ⟩ = ⟨ 𝟙 S , ( d I − A G ) 𝟙 T ⟩, 𝟙 𝟙 ⟨ 𝟙 S , d I 𝟙 T ⟩ = d | S ∩ T |.
𝟙 𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , A G 𝟙 T ⟩ = ∑ x ∑ y 𝟙 S ( x ) A G ( x , y ) 𝟙 T ( y ) = ∑ x ∑ y 𝟙 x y ∈ E = e ( S , T )
d n L K n = d I − d n J.
𝟙 𝟙 𝟙 𝟙 ⟨ 𝟙 S , d n J 𝟙 T ⟩ = d n ⟨ 𝟙 S , J 𝟙 T ⟩ = d n ∑ x ∑ y J ( x , y ) = d n | S | | T | .
𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 𝟙 | e ( S , T ) − d n | S | | T | | = | ⟨ 𝟙 S , ( d n L K n − L G ) 𝟙 T ⟩ | ≤ ∥ 𝟙 S ∥ ∥ ( d n L K n − L G ) 𝟙 T ∥ ≤ ∥ 𝟙 S ∥ ∥ ( d n L K n − L G ) ∥ ∥ 𝟙 T ∥ ≤ λ ∥ 𝟙 S ∥ ∥ 𝟙 T ∥ = λ | S | | T | To get the better bound, we should consider functions which are perpendicular to 1: balanced function 𝟙 f S = 𝟙 S − | S | n 1.
𝟙 𝟙 L G f S = L G ( 𝟙 S − α ) = L 𝟙 S.
| e ( S , T ) − d n | S | | T | | = | ⟨ f S , ( d n L K n − L G ) f T ⟩ | ≤ λ ∥ f S ∥ ∥ f T ∥
∥ f S ∥ 2 = | S | ( 1 − | S | n ) 2 + ( n − | S | ) ( − | S | n ) 2 = | S | ( 1 − 2 | S | n + | S | 2 n 2 ) + ( n − | S | ) | S | 2 n 2 = | S | − 2 | S | 2 n + | S | 3 n 2 + | S | 2 n − | S | 3 n 2 = | S | − | S | 2 n = n | S | − | S | 2 n = | S | | S c | n So
| e ( S , T ) − d n | S | | T | | ≤ | S | | S c | | T | | T c | . □
nothing: True

html: Theorem 4.9 (Alon-Boppana). Assuming that:
- G = ( V , E ) an ( n , d , λ )-graph
Then as n → ∞
λ ≥ 2 d − 1 − O ( 1 ) .
proof: Proof 1. Pick edge s t, pick r ∈ ℤ ≥ 0.
φ : V → ℝ,
φ ( x ) = { ( d − 1 ) − i ∕ 2 if x ∈ V i , i ≤ r 0 if x ∈ V i , i > r
q L ( φ ) = ⟨ φ , L φ ⟩ ⟨ φ , φ ⟩ ⟨ φ , φ ⟩ = ∑ i = 0 r | V i | ( d − 1 ) i .
⟨ φ , L φ ⟩ = ∑ x ∼ y ( φ ( x ) − φ ( y ) ) 2 = ∑ i = 0 r − 1 e ( V i , V i + 1 ) ( 1 ( d − 1 ) i ∕ 2 − 1 ( d − 1 ) ( i + 1 ) ∕ 2 ) 2 + e ( V r , V r + 1 ) ( d − 1 ) r = ∑ i = 0 r − 1 e ( V i , V i + 1 ) ( d − 1 ) i ( 1 − 1 d − 1 ) 2 + e ( V r , V r + 1 ) ( d − 1 ) r e ( V i , V i + 1 ) ≤ ( d − 1 ) | V i |. ⟨ φ , L φ ⟩ ≤ ∑ i = 0 r − 1 | V i | ( d − 1 ) i ( d − 1 − 1 ) 2 + | V r | ( d − 1 ) r ( d − 1 ) ( d − 1 − 1 ) 2 = ( d − 1 ) − 2 d − 1 + 1 = d − 2 d − 1 ⟨ φ , L φ ⟩ ≤ ( d − 2 d − 1 ) ∑ i = 0 r − 1 | V i | ( d − 1 ) i + ( d − 1 ) | V r | ( d − 1 ) r | V r | ≤ ( d − 1 ) | V r − 1 | ≤ ⋯ ≤ ( d − 1 ) r − i | V i | ⟹ | V r | ( d − 1 ) r ≤ 1 r ∑ i = 0 r | V i | ( d − 1 ) i ⟨ φ , L φ ⟩ ≤ ( d − 2 d − 1 ) ∑ i = 0 r | V i | ( d − 1 ) i + ( 2 d − 1 ) | V r | ( d − 1 ) r ≤ ( d − 2 d − 1 + 2 d − 1 − 1 r + 1 ) ⟨ φ , φ ⟩ ⟹ λ 2 ( L ) = min ⁡ dim ⁡ ⁡ W = 2 max ⁡ f ∈ W f ≠ 0 ⟨ f , L f ⟩ ⟨ f , f ⟩
Suppose G has 2 deges at distance > 2 r + 2.
f, f ′ as above. ⟨ f , f ′ ⟩ = 0.
Q L ( α f + β f ′ ) = Q L ( α f ) + Q L ( β f ′ ) .
Let W = span ⁡ { f , f ′ }.
λ 2 ( L ) ≤ max ⁡ ( α , β ) ≠ ( 0 , 0 ) Q L ( α f + β f ′ ) ∥ α f + β f ′ ∥ ≤ α 2 Q L ( f ) + β 2 Q L ( f ′ ) α 2 ∥ f ∥ + β 2 ∥ f ′ ∥ ≤ d − 2 d − 1 + 2 d − 1 − 1 r + 1 □
nothing: True

html: Corollary 4.10. For all d, there are finitely many ( n , d , λ )-graphs with λ < 2 d − 1.
proof: Proof 2. Tr ⁡ A 2 k = ∑ ⁡ x A 2 k ( x , x ). Note that
# { closed walks of length 2 k in G starting from x } .
is at least
# { closed walks of length 2 k in ∏ d starting from 0 }
(∏ ⁡ d is an infinite d-regular tree). The latter is at least
( d − 1 ) k 1 k + 1 2 k k ≈ ( 2 d − 1 ) 2 k + o ( 1 ) 2 2 k .
≤ ∑ i = 1 n λ i 2 k ≤ d 2 k + ( n − 1 ) λ 2 k .
Exercise: finish details. □
cloze1: True

html: Theorem 4.11. Assuming that:
- d = 2 l large enough
Then there is 𝜀 = 𝜀 d > 0 such that there are d-regular graphs (or multi-graphs) G n on n vertices with Φ ( G n ) ≥ 𝜀 for all sufficiently large n.
proof: Proof. If Φ ( G n ) < 𝜀 then there exists F ⊆ [ n ], r = | F | ≤ n 2, there exists F ′, F ⊆ F ′ and e ( F , F ′ ) = d | F | and | F ′ | = r + r ′, r ′ = ⌊ 𝜀 r ⌋.
ℙ ( Φ ( G n ) < 𝜀 ) < ∑ 1 ≤ r ≤ n 2 ∑ F ⊆ F ′ ⊆ [ n ] | F | = r | F ′ | = r + r ′ ℙ ( π i ( F ) ⊆ F ′ for all i ∈ [ l ] ) .
ℙ ( π 1 ( F ) ⊆ F ′ ) = r + r ′ r n r.
ℙ ≤ ∑ 1 ≤ r ≤ n 2 n ! r ! r ′ ! ( n − r − r ′ ) ! ( r + r ′ r n r ) l .
Fact 1: a k b k ≤ ( a b ) k if a ≤ b.
Proof: It is equivalent to
b a ⋅ b ( a − 1 ) ⋯ b ( a − k + 1 ) ≤ a b ⋅ a ( b − 1 ) ⋯ a ( b − k + 1 ) .
Compare the product term by term.
Fact 2: n ! ≥ ( n e ) n. Proof:
e n = ∑ k ≥ 0 n k k ! ≥ n n n ! .
Using these:
n ! r ! r ′ ! ( n − r − r ′ ) ! ≤ n r + r ′ r ! r ′ ! = n r + r ′ ( r + r ′ ) ! r + r ′ r ≤ ( 2 e ) r + r ′ ( n e + e ′ ) r + r ′ .
So
ℙ ≤ ∑ 1 ≤ r ≤ n 2 ( 2 e ) r + r ′ ( n r + r ′ ) r + r ′ ( r + r ′ n ) l r ≤ ∑ 1 ≤ r ≤ n 2 ( 2 e ) 2 r ( ( 1 + 𝜀 ) r n ) r ( l − 1 − 𝜀 )
Decompose as ∑ ⁡ 1 ≤ r ≤ n ∕ 2 = ∑ 1 ≤ r ≤ K + ∑ K < r ≤ n ∕ 2 = S 1 + S 2. Choose 𝜀 > 0 small so that γ = 1 + 𝜀 2 is small. Choose l large so that γ l − 1 − 𝜀 < 1 2 ( 2 e ) 2.
S 2 ≤ ∑ K < r ≤ n 2 ( 2 e ) 2 r ( ( 1 + 𝜀 ) 2 ) r ( l − 1 − 𝜀 ) ≤ ∑ K < r ≤ n 2 ( 1 2 ) r ≤ 1 2 K
Now S 1.
S 1 ≤ ∑ 1 ≤ r ≤ K ( 2 e ) 2 r ( ( 1 + 𝜀 ) r n ) r ( l − 1 − 𝜀 ) ≤ ( 2 K n ) l − 2 ∑ 1 ≤ r ≤ K ( 2 e ) 2 r ≤ c K ( K n ) l
Now let K = log ⁡ log ⁡ log ⁡ n, so this is ≤ O ( ( log ⁡ log ⁡ n ) n − l ( log ⁡ log ⁡ log ⁡ n ) l ) → 0. Also, S 1 ≤ 1 2 K term goes to 0. □
cloze1: True

html: Lemma 4.12. There is c = c d > 0 such that
ℙ ( G n is d -regular, i.e. G n is simple ) ≥ c − o ( 1 ) .
proof: Proof. If Φ ( G n ) < 𝜀 then there exists F ⊆ [ n ], r = | F | ≤ n 2, there exists F ′, F ⊆ F ′ and e ( F , F ′ ) = d | F | and | F ′ | = r + r ′, r ′ = ⌊ 𝜀 r ⌋.
ℙ ( Φ ( G n ) < 𝜀 ) < ∑ 1 ≤ r ≤ n 2 ∑ F ⊆ F ′ ⊆ [ n ] | F | = r | F ′ | = r + r ′ ℙ ( π i ( F ) ⊆ F ′ for all i ∈ [ l ] ) .
ℙ ( π 1 ( F ) ⊆ F ′ ) = r + r ′ r n r.
ℙ ≤ ∑ 1 ≤ r ≤ n 2 n ! r ! r ′ ! ( n − r − r ′ ) ! ( r + r ′ r n r ) l .
Fact 1: a k b k ≤ ( a b ) k if a ≤ b.
Proof: It is equivalent to
b a ⋅ b ( a − 1 ) ⋯ b ( a − k + 1 ) ≤ a b ⋅ a ( b − 1 ) ⋯ a ( b − k + 1 ) .
Compare the product term by term.
Fact 2: n ! ≥ ( n e ) n. Proof:
e n = ∑ k ≥ 0 n k k ! ≥ n n n ! .
Using these:
n ! r ! r ′ ! ( n − r − r ′ ) ! ≤ n r + r ′ r ! r ′ ! = n r + r ′ ( r + r ′ ) ! r + r ′ r ≤ ( 2 e ) r + r ′ ( n e + e ′ ) r + r ′ .
So
ℙ ≤ ∑ 1 ≤ r ≤ n 2 ( 2 e ) r + r ′ ( n r + r ′ ) r + r ′ ( r + r ′ n ) l r ≤ ∑ 1 ≤ r ≤ n 2 ( 2 e ) 2 r ( ( 1 + 𝜀 ) r n ) r ( l − 1 − 𝜀 )
Decompose as ∑ ⁡ 1 ≤ r ≤ n ∕ 2 = ∑ 1 ≤ r ≤ K + ∑ K < r ≤ n ∕ 2 = S 1 + S 2. Choose 𝜀 > 0 small so that γ = 1 + 𝜀 2 is small. Choose l large so that γ l − 1 − 𝜀 < 1 2 ( 2 e ) 2.
S 2 ≤ ∑ K < r ≤ n 2 ( 2 e ) 2 r ( ( 1 + 𝜀 ) 2 ) r ( l − 1 − 𝜀 ) ≤ ∑ K < r ≤ n 2 ( 1 2 ) r ≤ 1 2 K
Now S 1.
S 1 ≤ ∑ 1 ≤ r ≤ K ( 2 e ) 2 r ( ( 1 + 𝜀 ) r n ) r ( l − 1 − 𝜀 ) ≤ ( 2 K n ) l − 2 ∑ 1 ≤ r ≤ K ( 2 e ) 2 r ≤ c K ( K n ) l
Now let K = log ⁡ log ⁡ log ⁡ n, so this is ≤ O ( ( log ⁡ log ⁡ n ) n − l ( log ⁡ log ⁡ log ⁡ n ) l ) → 0. Also, S 1 ≤ 1 2 K term goes to 0. □
cloze1: True

html: Lemma 4.13. If G n is d-regular, then there exists 𝜀 = 𝜀 d > 0 such that
ℙ ( Φ ( G n ) < 𝜀 ) → 0 .
proof: Proof. If Φ ( G n ) < 𝜀 then there exists F ⊆ [ n ], r = | F | ≤ n 2, there exists F ′, F ⊆ F ′ and e ( F , F ′ ) = d | F | and | F ′ | = r + r ′, r ′ = ⌊ 𝜀 r ⌋.
ℙ ( Φ ( G n ) < 𝜀 ) < ∑ 1 ≤ r ≤ n 2 ∑ F ⊆ F ′ ⊆ [ n ] | F | = r | F ′ | = r + r ′ ℙ ( π i ( F ) ⊆ F ′ for all i ∈ [ l ] ) .
ℙ ( π 1 ( F ) ⊆ F ′ ) = r + r ′ r n r.
ℙ ≤ ∑ 1 ≤ r ≤ n 2 n ! r ! r ′ ! ( n − r − r ′ ) ! ( r + r ′ r n r ) l .
Fact 1: a k b k ≤ ( a b ) k if a ≤ b.
Proof: It is equivalent to
b a ⋅ b ( a − 1 ) ⋯ b ( a − k + 1 ) ≤ a b ⋅ a ( b − 1 ) ⋯ a ( b − k + 1 ) .
Compare the product term by term.
Fact 2: n ! ≥ ( n e ) n. Proof:
e n = ∑ k ≥ 0 n k k ! ≥ n n n ! .
Using these:
n ! r ! r ′ ! ( n − r − r ′ ) ! ≤ n r + r ′ r ! r ′ ! = n r + r ′ ( r + r ′ ) ! r + r ′ r ≤ ( 2 e ) r + r ′ ( n e + e ′ ) r + r ′ .
So
ℙ ≤ ∑ 1 ≤ r ≤ n 2 ( 2 e ) r + r ′ ( n r + r ′ ) r + r ′ ( r + r ′ n ) l r ≤ ∑ 1 ≤ r ≤ n 2 ( 2 e ) 2 r ( ( 1 + 𝜀 ) r n ) r ( l − 1 − 𝜀 )
Decompose as ∑ ⁡ 1 ≤ r ≤ n ∕ 2 = ∑ 1 ≤ r ≤ K + ∑ K < r ≤ n ∕ 2 = S 1 + S 2. Choose 𝜀 > 0 small so that γ = 1 + 𝜀 2 is small. Choose l large so that γ l − 1 − 𝜀 < 1 2 ( 2 e ) 2.
S 2 ≤ ∑ K < r ≤ n 2 ( 2 e ) 2 r ( ( 1 + 𝜀 ) 2 ) r ( l − 1 − 𝜀 ) ≤ ∑ K < r ≤ n 2 ( 1 2 ) r ≤ 1 2 K
Now S 1.
S 1 ≤ ∑ 1 ≤ r ≤ K ( 2 e ) 2 r ( ( 1 + 𝜀 ) r n ) r ( l − 1 − 𝜀 ) ≤ ( 2 K n ) l − 2 ∑ 1 ≤ r ≤ K ( 2 e ) 2 r ≤ c K ( K n ) l
Now let K = log ⁡ log ⁡ log ⁡ n, so this is ≤ O ( ( log ⁡ log ⁡ n ) n − l ( log ⁡ log ⁡ log ⁡ n ) l ) → 0. Also, S 1 ≤ 1 2 K term goes to 0. □

html: Theorem 4.14 (Lubotsky-Phillips-Sanak / Margoulis). Assuming that:
- p prime
- d = p + 1
- n arbitrarily large
Then there exists a ( n , d , 2 d − 1 )-graph.
proof: Proof.
Ĝ A Ĝ S = ( A S + A S S − A S − A S S + )
Let A φ = λ φ. Then
Ĝ A Ĝ S ( φ φ ) = ( A S + φ + A S − φ A S − φ + A S + φ ) = ( A φ A φ ) = ( λ φ λ φ ) = λ ( φ φ ) .
Let S η = μ η. Now
Ĝ A Ĝ S ( η − η ) = ( A S + η − A S − η A S − η − A S + η ) = ( S η − S η ) = ( μ η − μ η ) = μ ( η − η ) . □
nothing: True

html: Theorem 4.15 (Marcus, Spielman, Srivastava). Assuming that:
- d ≥ 3
Then there are ( n , d , 2 d − 1 )-bipartite graphs for arbitrarily large n.
proof: Proof.
Ĝ A Ĝ S = ( A S + A S S − A S − A S S + )
Let A φ = λ φ. Then
Ĝ A Ĝ S ( φ φ ) = ( A S + φ + A S − φ A S − φ + A S + φ ) = ( A φ A φ ) = ( λ φ λ φ ) = λ ( φ φ ) .
Let S η = μ η. Now
Ĝ A Ĝ S ( η − η ) = ( A S + η − A S − η A S − η − A S + η ) = ( S η − S η ) = ( μ η − μ η ) = μ ( η − η ) . □
nothing: True

html: Definition 4.16 (2-lift). A 2-lift of a graph G = ( V , E ) is a graph Ĝ Ê Ĝ = ( V ^ , Ê ) with
- x ∈ V ⟹ x 0 , x 1 ∈ V ^.
- x y ∈ E ⟹ either Ê x 0 y 0 , x 1 y 1 ∈ Ê or Ê x 0 y 1 , x 1 y 0 ∈ Ê.
(and no other vertices or edges).
nothing: True

html: Definition 4.17 (Signing). S : V × V → ℝ is a signing of G if
S ( x , y ) = { ± 1 if A ( x , y ) = 1 0 if A ( x , y ) = 0
and S ( x , y ) = S ( y , x ) (symmetric). So can think of S as a function E → { ± 1 }.
nothing: True

html: Lemma 4.18. The eigenvalues of Ĝ Ĝ are the eigenvalues of A G (old) together with the eigenvalues of S (new).
proof: Proof.
Ĝ A Ĝ S = ( A S + A S S − A S − A S S + )
Let A φ = λ φ. Then
Ĝ A Ĝ S ( φ φ ) = ( A S + φ + A S − φ A S − φ + A S + φ ) = ( A φ A φ ) = ( λ φ λ φ ) = λ ( φ φ ) .
Let S η = μ η. Now
Ĝ A Ĝ S ( η − η ) = ( A S + η − A S − η A S − η − A S + η ) = ( S η − S η ) = ( μ η − μ η ) = μ ( η − η ) . □
cloze1: True

html: Theorem 4.20 (Bilu, Linial). Can find signings S with eigenvalues λ satisfying | λ | = O ( d ( log ⁡ d ) 3 ).
proof: Theorem 4.21 implies Theorem 4.15 .
- Start with K d , d.
- Keep applying Theorem 4.21 to find signing.
- Build lift with that signing.
- 2-lift of bipartite graph is bipartite.
- Spectrum of adjacency matrix of bipartite graph is symmetric around 0. □
nothing: True

html: Theorem 4.21 (Marcusm, Spielman, Srivastava). Assuming that:
- G is a d-regular graph
Then there exists a signing with eigenvalues λ with λ ≤ 2 d − 1.
proof: Theorem 4.21 implies Theorem 4.15 .
- Start with K d , d.
- Keep applying Theorem 4.21 to find signing.
- Build lift with that signing.
- 2-lift of bipartite graph is bipartite.
- Spectrum of adjacency matrix of bipartite graph is symmetric around 0. □
nothing: True

html: Theorem 4.22 (Godsil-Gutman, 80s).
𝔼 S ∼ { ± 1 } det ⁡ ( x I − A s ) = μ G ( x ) ,
where
μ G ( x ) = ∑ k ≥ 0 x n − 2 k ( − 1 ) k m k ( G ) ,
where m k ( G ) is the number of matchings in G with k edges.
proof: Proof. Assume f and g without repeated or common roots (general case requires more work and details checking).
- ⇐ Let h t ( x ) = t f ( x ) + ( t − 1 ) g ( x ) for t ∈ ( 0 , 1 ). We know these are real rooted, and waht to show that f, g have a common interlacement. Let λ i ( t ) be the i-th root of h t ( x ). λ i ( t ) includes ( λ i ( 0 ) , λ i ( 1 ) ) ⊆ ℝ.
Claim: ( λ I ( 0 ) , λ I ( 1 ) ) are disjoint.
Suppose not. Let λ k be a root of f and λ k ∈ ( λ I ( 0 ) , λ I ( 1 ) ). So there exists t ∈ ( 0 , 1 ) such that λ I ( t ) = λ k.
h t ( λ k ) = 0 = t f ( λ k ) + ( 1 − t ) g ( λ k ) ,
so g ( λ k ) = 0, contradiction as we assumed no common roots.
- ⇒
The dots represent the roots of the polynomial that interlaces them. By monicness, we get the blue and green +s and −s. Then get the orange ones, and use intermediate value theorem. □
nothing: True

html: Theorem 4.23 (Heilman-Lieb, 72). Assuming that:
- G is d-regular
Then
maxroot ⁡ μ G ( x ) ≤ 2 d − 1 .
proof: Proof. Assume f and g without repeated or common roots (general case requires more work and details checking).
- ⇐ Let h t ( x ) = t f ( x ) + ( t − 1 ) g ( x ) for t ∈ ( 0 , 1 ). We know these are real rooted, and waht to show that f, g have a common interlacement. Let λ i ( t ) be the i-th root of h t ( x ). λ i ( t ) includes ( λ i ( 0 ) , λ i ( 1 ) ) ⊆ ℝ.
Claim: ( λ I ( 0 ) , λ I ( 1 ) ) are disjoint.
Suppose not. Let λ k be a root of f and λ k ∈ ( λ I ( 0 ) , λ I ( 1 ) ). So there exists t ∈ ( 0 , 1 ) such that λ I ( t ) = λ k.
h t ( λ k ) = 0 = t f ( λ k ) + ( 1 − t ) g ( λ k ) ,
so g ( λ k ) = 0, contradiction as we assumed no common roots.
- ⇒
The dots represent the roots of the polynomial that interlaces them. By monicness, we get the blue and green +s and −s. Then get the orange ones, and use intermediate value theorem. □
nothing: True

html: Definition 4.24 (Interlacing). Let f be a real rooted polynomial of degree n with roots α 1 , … , α n and g a real rooted polynomial of degree n − 1 with roots β 1 , … , β n − 1. We say g interlaces f if
α 1 ≤ β 1 ≤ α 2 ≤ ⋯ ≤ β n − 2 ≤ α n − 1 ≤ β n − 1 ≤ α n .
nothing: True

html: Definition 4.25 (Common interlacement). We say that real rooted polynomials f, g of degree n have a common interlacement if there is a polynomial h of degree n + 1 such that f and g both interlace h. In other words, if the roots of f and g are α 1 ≤ ⋯ α n and β 1 ≤ ⋯ ≤ β n respectively, then they have a common interlacement if and only if there are some γ 0 ≤ ⋯ ≤ γ n such that
γ 0 ≤ α 1 , β 1 ≤ γ 1 ≤ α 2 , β 2 ≤ γ 2 ≤ ⋯ ≤ γ n − 1 ≤ α n , β n ≤ γ n .
nothing: True

html: Theorem 4.26 (Fell 80). Assuming that:
- f, g are real rooted
- both degree n, monic
Then f and g have a common interlacing if and only if every convex combination of f and g are real rooted.
proof: Proof. Assume f and g without repeated or common roots (general case requires more work and details checking).
- ⇐ Let h t ( x ) = t f ( x ) + ( t − 1 ) g ( x ) for t ∈ ( 0 , 1 ). We know these are real rooted, and waht to show that f, g have a common interlacement. Let λ i ( t ) be the i-th root of h t ( x ). λ i ( t ) includes ( λ i ( 0 ) , λ i ( 1 ) ) ⊆ ℝ.
Claim: ( λ I ( 0 ) , λ I ( 1 ) ) are disjoint.
Suppose not. Let λ k be a root of f and λ k ∈ ( λ I ( 0 ) , λ I ( 1 ) ). So there exists t ∈ ( 0 , 1 ) such that λ I ( t ) = λ k.
h t ( λ k ) = 0 = t f ( λ k ) + ( 1 − t ) g ( λ k ) ,
so g ( λ k ) = 0, contradiction as we assumed no common roots.
- ⇒
The dots represent the roots of the polynomial that interlaces them. By monicness, we get the blue and green +s and −s. Then get the orange ones, and use intermediate value theorem. □
nothing: True

html: Corollary 4.27. Assuming that:
- f, g are real rooted of degree n
- have a common interlacing
Then for all t ∈ [ 0 , 1 ]
min ⁡ { maxroot ⁡ ( f ) , maxroot ⁡ ( g ) } ≤ maxroot ⁡ ( t f ( x ) + ( 1 − t ) g ( x ) ) .
proof: Proof.
- ⇒ If p not stable, then there exists z 0 , … , z n ∈ H with p ( z 1 , … , z n ) = 0, z j = b j + i a j, a j > 0. Then p ( a i + b ) = 0, t = i.
- ⇐ Suppose ∃ ⁡ a ∈ ℝ ≥ 0 n, b ∈ ℝ n, t ∈ ℂ ∖ ℝ with p ( a t + b ) = 0. Assume Im ⁡ t > 0. z j + a j t + b j ∈ H. p ( z 1 , … , z n ) = p ( a t + b ) = 0.
□
cloze1: True

html: Theorem 4.28 (Marcus, Spielman, Srivastava (real rooted)). For every ρ 1 , … , ρ m ∈ [ − 1 , 1 ] the following polynomial is real rooted
χ ρ 1 , … , ρ m ( x ) = ∑ S ∈ { ± 1 } m det ⁡ ( x I − A s ) ∏ J : s J = 1 ( 1 + ρ J 2 ) ∏ J : S J = − 1 ( 1 − ρ J 2 ) .
proof: Proof.
- ⇒ If p not stable, then there exists z 0 , … , z n ∈ H with p ( z 1 , … , z n ) = 0, z j = b j + i a j, a j > 0. Then p ( a i + b ) = 0, t = i.
- ⇐ Suppose ∃ ⁡ a ∈ ℝ ≥ 0 n, b ∈ ℝ n, t ∈ ℂ ∖ ℝ with p ( a t + b ) = 0. Assume Im ⁡ t > 0. z j + a j t + b j ∈ H. p ( z 1 , … , z n ) = p ( a t + b ) = 0.
□
nothing: True

html: Theorem 4.29 (Marcus, Spielman, Srivastava (matrix)). Assuming that:
- r 1 , … , r m ∈ ℝ n are independent random vectors, whose support has ≤ 2 points
Then
𝔼 det ⁡ ( x I − ∑ j = 1 m r j r j ⊤ ⁡ )
is real rooted.
proof: Proof.
- ⇒ If p not stable, then there exists z 0 , … , z n ∈ H with p ( z 1 , … , z n ) = 0, z j = b j + i a j, a j > 0. Then p ( a i + b ) = 0, t = i.
- ⇐ Suppose ∃ ⁡ a ∈ ℝ ≥ 0 n, b ∈ ℝ n, t ∈ ℂ ∖ ℝ with p ( a t + b ) = 0. Assume Im ⁡ t > 0. z j + a j t + b j ∈ H. p ( z 1 , … , z n ) = p ( a t + b ) = 0.
□
nothing: True

html: Definition 4.30 (Real stable). A polynomial p ( z 1 , … , z n ) ∈ ℝ [ z 1 , … , z n ] is real stable if p ( z 1 , … , z n ) ≠ 0 for all ( z 1 , … , z n ) ∈ H n, H = { z ∈ ℂ | Im ⁡ z > 0 }.
nothing: True

html: Proposition 4.31 (Stable iff real rooted). p ( z 1 , … , z n ) is real stable if and only if for all ℝ ≥ 0 n, b ∈ ℝ n, the polynomial t ↦ p ( a t + b ) is real rooted.
proof: Proof.
- ⇒ If p not stable, then there exists z 0 , … , z n ∈ H with p ( z 1 , … , z n ) = 0, z j = b j + i a j, a j > 0. Then p ( a i + b ) = 0, t = i.
- ⇐ Suppose ∃ ⁡ a ∈ ℝ ≥ 0 n, b ∈ ℝ n, t ∈ ℂ ∖ ℝ with p ( a t + b ) = 0. Assume Im ⁡ t > 0. z j + a j t + b j ∈ H. p ( z 1 , … , z n ) = p ( a t + b ) = 0.
□
nothing: True

html: Proposition 4.32 (Stability of real stable). Assuming that:
- p ( z 1 , … , z n ) is real stable
Then the following are also:
- p ( z σ ( 1 ) , … , z σ ( n ) ), σ ∈ S n.
- p ( a z 1 , z 2 , … , z n ), a ∈ ℝ ≥ 0.
- p ( z 2 , z 2 , z 3 , … , z n ).
- p ( c , z 2 , … , z n ), c ∈ H ∪ ℝ.
- z 1 d 1 p ( − 1 z 1 , z 2 , … , z n ).
- ∂ z 1 p ( z 1 , … , z n ).
- MAP ⁡ ( p ( z 1 , … ⁡ , z n ) ). MAP ⁡ ( z 1 z 2 + z 2 z 3 2 + 2 z 1 z 4 + z 2 z 3 2 ) = z 1 z 2 + 2 z 1 z 4.
- If p , q are real stable, then so is p q.
proof: Proof. Let a ∈ ℝ ≥ 0 n, b ∈ ℝ n. Assume positive definite instead of positive semi definite.
det ⁡ ( B + ∑ j = 1 n ( a j t + b j ) A j ) = det ⁡ ( ( ∑ j = 1 n a j A j ) ⏟ = : A t + ( ∑ j = 1 n b j A j + B ) ⏟ = : C )
A is positive definite, and C is symmetric. So
= det ⁡ ( A t + C ) = det ⁡ ( A 1 2 ( t I + A − 1 2 C A − 1 2 ) A 1 2 ) = det ⁡ A det ⁡ ( t I + A − 1 2 C A − 1 2 )
The roots are eigenvalues of a real symmetric matrix, hence real. □
nothing: True

html: Proposition 4.33 (Mother of all stable polynomials). Assuming that:
- B ∈ ℝ d × d symmetric matrix
- A 1 , … , A m ∈ ℝ d × d positive semi definite
Then det ⁡ ( B + z 1 A 1 + ⋯ + z n A n ) is real stable.
proof: Proof. Let a ∈ ℝ ≥ 0 n, b ∈ ℝ n. Assume positive definite instead of positive semi definite.
det ⁡ ( B + ∑ j = 1 n ( a j t + b j ) A j ) = det ⁡ ( ( ∑ j = 1 n a j A j ) ⏟ = : A t + ( ∑ j = 1 n b j A j + B ) ⏟ = : C )
A is positive definite, and C is symmetric. So
= det ⁡ ( A t + C ) = det ⁡ ( A 1 2 ( t I + A − 1 2 C A − 1 2 ) A 1 2 ) = det ⁡ A det ⁡ ( t I + A − 1 2 C A − 1 2 )
The roots are eigenvalues of a real symmetric matrix, hence real. □
nothing: True

html: Theorem 4.34 (Godsil). Assuming that:
- G is d-regular
- λ 1 ≤ ⋯ ≤ λ n are the roots of μ G ( x )
Then
∑ k = 1 n λ k l = ∑ a W a l ( G ) ,
where W a l ( G ) is the number of closed walks of length l from a in the path tree T a ( G ) of G.
proof: Proof of ?? implies Theorem 4.23 . W a l ( G ) ≤ W a l ( ∏ ⁡ d ) ≤ ( 2 d − 1 + o l ( 1 ) ) l.
λ n l ≤ ∑ ⁡ λ k l = ∑ a W a l ( G ) ≤ n ( 2 d − 1 + o l ( 1 ) ) l.
λ n ≤ n 1 l ( 2 d − 1 + o l ( 1 ) ).
Take l → ∞. □
nothing: True

html: Definition 4.35 (Path tree). Example: T a ( G )
nothing: True