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

spectral graph theoryeigenvaluesrandom walks

Mathematics Subject Classification ID

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

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

• A Spectral Technique for Coloring Random 3-Colorable Graphs
• A geometric approach to on-diagonal heat kernel lower bounds on groups.
• 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
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(5)

• On the eigenspaces of lamplighter random walks and percolation clusters on 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 second eigenvalue and random walks in random \(d\)-regular 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)