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

DOI10.5802/AFST.1465MaRDI QIDQ5963354zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Sharp bounds on random walk eigenvalues via spectral embedding
• High-order random walks and generalized Laplacians on hypergraphs
• High-ordered random walks and generalized Laplacians on hypergraphs
• scientific article; zbMATH DE number 6902684
• scientific article; zbMATH DE number 850069

Cites work

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

Cited in

(5)

• On the second eigenvalue and random walks in random d-regular graphs
• Spectral concentration and greedy k-clustering
• Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
• Sharp bounds on random walk eigenvalues via spectral embedding
• On the eigenspaces of lamplighter random walks and percolation clusters on graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963354)