Spectral Independence Lecture Notes
share
These are self-contained lecture notes for spectral independence. For an n-vertex graph, the spectral independence condition is a bound on the maximum eigenvalue of the n× n influence matrix whose entries capture the influence between pairs of vertices, it is closely related to the covariance matrix. We will present recent results showing that spectral independence implies the mixing time of the Glauber dynamics is polynomial (where the degree of the polynomial depends on certain parameters). The proof utilizes local-to-global theorems which we will detail in these notes. Finally, we will present more recent results showing that spectral independence implies an optimal bound on the relaxation time (inverse spectral gap) and with some additional conditions implies an optimal mixing time bound of O(nlogn) for the Glauber dynamics. Our focus is on the analysis of the spectral gap of the Glauber dynamics from a functional analysis perspective of analyzing the associated local and global variance, and we present proofs of the associated local-to-global theorems from this same Markov chain perspective.
READ FULL TEXT