Abstract
The Cheeger-Alon-Milman inequality provides an algorithmic method to verify that a graph is an edge-expander, by certifying that its expansion (minimum ratio of the number of edges leaving a subset of vertices to the total number of edge incident to the subset) lies between $\lambda_2$ and $\sqrt{2 \lambda_2}$. In this talk, we present a Cheeger inequality for vertex expansion (minimum ratio of number of vertices adjacent to a subset to the size of the subset), a parameter of fundamental importance, which is also NP-hard and approximable to within $O(\sqrt{\log n}) OPT$ in polynomial-time. The analog of $\lambda_2$ is $\lambda_\infty$, a quantity defined by Bobkov, Houdre and Tetali, which provides a lower bound on the vertex expansion, and can be approximated by an SDP. The resulting algorithmic inequality says that the vertex expansion is sandwiched between $\lambda_\infty$ and $\sqrt{log d \lambda_infty}$, where $d$ is the maximum degree of the graph. Moreover, this bound is the best possible under the Small Set Expansion Hypothesis of Raghavendra and Steurer, implying in particular that unlike edge expansion, constant vertex expansion cannot be certified in polynomial time. We will also discuss generalizations to hypergraphs by Louis.
This is joint work with Anand Louis and Prasad Raghavendra.