Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
The celebrated Cheeger's Inequality [AM85,a86] establishes a bound on the expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs. It has remained open to …