Prefer a chat interface with context about you and your work?
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph G,where φV(G) denotes the robust vertex expansion of G and φ(G) denotes the edge expansion of G. The second generalization relates the second eigenvalue …