2012/04/20 by Ryan O'Donnell, Ryan O’Donnell, O'Donnell, Ryan +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #cs.DS
paper · pdf · doi:10.48550/arxiv.1204.4688
openalex publication_date 2012/04/20 · arxiv created 2013/11/04 · arxiv updated 2013/11/05 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Consider a finite irreducible Markov chain with invariant distribution π. We use the inner product induced by π and the associated heat operator to simplify and generalize some results related to graph partitioning and the small-set expansion problem. For example, Steurer showed a tight connection between the number of small eigenvalues of a graph's Laplacian and the expansion of small sets in that graph. We give a simplified proof which generalizes to the nonregular, directed case. This result implies an approximation algorithm for an "analytic" version of the Small-Set Expansion Problem, which, in turn, immediately gives an approximation algorithm for Small-Set Expansion. We also give a simpler proof of a lower bound on the probability that a random walk stays within a set; this result was used in some recent works on finding small sparse cuts.