Quantitative near-bipartiteness: mixing, parity breaking, max cut, and eigenvalue gap

Quantitative near-bipartiteness: mixing, parity breaking, max cut, and eigenvalue gap

Quantitative near-bipartiteness: mixing, parity breaking, max cut, and eigenvalue gap

Tuesday, June 13, 2023
  • Lecturer: Jonathan Hermon (UBC)
  • Location: Meyer building (electrical engeneering), room 861
Abstract:
In this talk I'll present some general quantitative near-bipartite results for reversible Markov chains. It turns out that if the total variation of a reversible transition matrix P is much larger than that of its lazy version (I+P)/2 then P must satisfy certain strong near-bipartite behaviors, which for most starting states prevail for order of the mixing time number of steps. Namely, if f is an eigenvector corresponding to the smallest eigenvalue of P, then the chain is likely to alternate between being at A:={x : f(x) is positive} at even times to being at the complement at odd times, or vice-versa, for order mixing time number of steps. Moreover, the mixing behavior in this case is in a sense completely governed by the probability the chain assigns A. We also give a probabilistic characterization of the absolute spectral gap of P and show that P can have at most one (negative) eigenvalue whose distance from -1 is at most a small absolute constant the spectral gap (= 1 - second largest e.v. of P)
Print to PDF