Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs

Whether or not the Sparsest Cut problem admits an efficient 𝑂(1)-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture. We design an 𝑂(1)-approximation algorithm to Sparsest Cut for the class of Cayley graphs over Abelian groups, running in time 𝑛^𝑂(1) · exp{𝑑^𝑂(𝑑)} where 𝑑 is the degree of the graph. 

Previous work has centered on solving cut problems on graphs which are “expander-like” in various senses, such as being a small-set expander or having low threshold rank. In contrast, low-degree Abelian Cayley graphs are natural examples of non-expanding graphs far from these assumptions (e.g. the cycle). We demonstrate that spectral and semidefinite programming-based methods can still succeed in these graphs by analyzing an eigenspace enumeration algorithm which searches for a sparse cut among the low eigenspace of the Laplacian matrix. We dually interpret this algorithm as searching for a hyperplane cut in a low-dimensional embedding of the graph. 

In order to analyze the algorithm, we prove a bound of 𝑑^𝑂(𝑑) on the number of eigenvalues “near” 𝜆₂ for connected degree-𝑑 Abelian Cayley graphs. We obtain a tight bound of 2^Θ(𝑑) on the multiplicity of 𝜆₂ itself which improves on a previous bound of 2^{𝑂(𝑑^2)} by Lee and Makarychev.