Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks

DOI10.5802/afst.1465zbMath1349.05208OpenAlexW2564351170MaRDI QIDQ5963354

Shayan Oveis Gharan

Publication date: 19 February 2016

Published in: Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=AFST_2015_6_24_4_801_0/

zbMATH Keywords

eigenvaluesrandom walksspectral graph theory

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81)

Related Items (1)

Spectral concentration and greedy \(k\)-clustering

Cites Work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• On eigenfunctions of Markov processes on trees
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• On hyperboundedness and spectrum of Markov operators
• Hypercontra ctive semigroups and two dimensional self-coupled Bose fields
• A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Partitioning into Expanders
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Improved Cheeger's inequality
• The Eigenvalues of a Graph and Its Chromatic Number
• A geometric approach to on-diagonal heat kernel lower bounds on groups.

This page was built for publication: Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks