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

DOI10.5802/AFST.1465zbMATH Open1349.05208OpenAlexW2564351170MaRDI QIDQ5963354FDOQ5963354

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/

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

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)

Cites Work

• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• On eigenfunctions of Markov processes on trees
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• On hyperboundedness and spectrum of Markov operators
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Improved Cheeger's inequality
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• The Eigenvalues of a Graph and Its Chromatic Number
• Partitioning into Expanders
• A geometric approach to on-diagonal heat kernel lower bounds on groups.
• Hypercontra ctive semigroups and two dimensional self-coupled Bose fields
• 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
• A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs

Cited In (4)

• Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
• Spectral concentration and greedy \(k\)-clustering
• On the eigenspaces of lamplighter random walks and percolation clusters on graphs
• 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)