Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs

d'Orsi, Tommaso; Jones, Chris; Ruotolo, Jake; Vadhan, Salil; Zhang, Jiyu

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.16

Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs

Tommaso d’Orsi

Bocconi University, Milan, Italy Chris Jones

Bocconi University, Milan, Italy Jake Ruotolo

Harvard University, Cambridge, MA, USA Salil Vadhan

Harvard University, Cambridge, MA, USA Jiyu Zhang

Bocconi University, Milan, Italy

Abstract

Whether or not the Sparsest Cut problem admits an efficient $O(1)$ -approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture.

Revisiting spectral algorithms for Sparsest Cut, we present a novel, simple algorithm that combines eigenspace enumeration with a new algorithm for the Cut Improvement problem. The runtime of our algorithm is parametrized by a quantity that we call the solution dimension $\textup{{SD}}_{\varepsilon}(G)$ : the smallest $k$ such that the subspace spanned by the first $k$ Laplacian eigenvectors contains all but $\varepsilon$ fraction of a sparsest cut.

Our algorithm matches the guarantees of prior methods based on the threshold-rank paradigm, while also extending beyond them. To illustrate this, we study its performance on low degree Cayley graphs over Abelian groups – canonical examples of graphs with poor expansion properties.

We prove that low degree Abelian Cayley graphs have small solution dimension, yielding an algorithm that computes a $(1+\varepsilon)$ -approximation to the uniform Sparsest Cut of a degree- $d$ Cayley graph over an Abelian group of size $n$ in time $n^{O(1)}\cdot\exp\{(d/\varepsilon)^{O(d)}\}$ . Along the way to bounding the solution dimension of Abelian Cayley graphs, we analyze their sparse cuts and spectra, proving that the collection of $O(1)$ -approximate sparsest cuts has an $\varepsilon$ -net of size $\exp\{(d/\varepsilon)^{O(d)}\}$ and that the multiplicity of $\lambda_{2}$ is bounded by $2^{O(d)}$ . The latter bound is tight and improves on a previous bound of $2^{O(d^{2})}$ by Lee and Makarychev.

Keywords and phrases:

Sparsest Cut, Spectral Graph Theory, Cayley Graphs, Approximation Algorithms

Category:

APPROX

Funding:

Chris Jones: CJ is supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement Nos. 834861 and 101019547). CJ is also a member of the Bocconi Institute for Data Science and Analytics (BIDSA).

Salil Vadhan: SV was a Visiting Researcher at the Bocconi University Department of Computing Sciences, supported by Luca Trevisan’s ERC Project GA-834861.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis ; Mathematics of computing

\rightarrow

Spectra of graphs

Related Version:

Full Version: https://arxiv.org/abs/2412.17115

Acknowledgements:

We deeply thank Luca Trevisan for his motivation and wisdom on this problem, and for suggesting to look into Abelian Cayley graphs. CJ and JZ thank Lucas Pesenti and Robert Wang for discussions. We thank Madhu Sudan for pointing us to [6].

Funding:

JR and SV are supported in part by a Simons Investigator Award to Salil Vadhan. Work began while JR and SV were visitors at Bocconi University.

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.16

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

For an undirected graph $G$ , the sparsest cut measures how poor of an expander the graph is, characterizing how slowly random walks on $G$ mix. For simplicity in this introduction, we will state our definitions just for the case of regular graphs:

Definition 1 (Sparsest Cut).

For a $d$ -regular graph $G$ on $n$ vertices and a partition $(Q,\bar{Q})$ of its vertex set $V(G)$ , the (normalized) density of the cut $(Q,\bar{Q})$ is defined as:

\displaystyle\psi_{G}(Q):=\frac{|E(Q,\bar{Q})|}{|Q|\cdot|\bar{Q}|}\cdot\frac{n% }{d}.

The sparsest cut problem is, given $G$ , to find $Q\subseteq V(G)$ that minimizes $\psi_{G}(Q).$ We write $\psi(G)$ to denote the minimum value of $\psi_{G}(Q)$ over all cuts $(Q,\bar{Q})$ .

The normalization factor of $n/d$ ensures that the largest possible value of $\psi(G)$ is $1$ , because for a randomly chosen cut $Q$ , the expectation of $|E(Q,\bar{Q})|$ is $nd/4$ , and the expectation of $|Q|\cdot|\bar{Q}|$ is $n^{2}/4$ . We’ll often switch back and forth between $\psi(G)$ and the closely related quantity of conductance, defined as

\phi(G)=\min_{|Q|\leqslant n/2}\phi_{G}(Q),\quad\text{ where }\quad\phi_{G}(Q)% =\frac{|E(Q,\bar{Q})|}{d\cdot|Q|}.

We have $\phi(G)\leqslant\psi(G)\leqslant 2\cdot\phi(G)$ , so the problem of approximating conductance is equivalent to the problem of approximating sparsest cut, up to multiplying the approximation factor by 2. Via known reductions, up to a constant factor of approximation, sparsest cut is also equivalent to approximating several other graph parameters such as edge expansion and balanced separator [5].

Because of its centrality to algorithms, computational complexity, combinatorics, and geometry, efficient algorithms for sparsest cut have been the main focus of a long line of work. A polynomial-time $O(\log n)$ -approximation algorithm was obtained via a linear programming relaxation by Leighton and Rao [34], and later improved to $O(\sqrt{\log n})$ by Arora, Rao, and Vazirani (ARV) [5] via semidefinite programming. To this day, the ARV algorithm remains the state-of-the-art for general graphs.

A central challenge to resolving the approximability of sparsest cut is its intricate relationship with the Unique Games Conjecture (UGC) and the Small Set Expansion Hypothesis (SSEH), themselves outstanding open problems with a close connection [25, 41, 42]. Assuming the SSEH, sparsest cut does not have a polynomial-time $O(1)$ -approximation algorithm [42] (the same holds for “non-uniform” sparsest cut assuming the UGC [13, 26, 4]). Thus we have some evidence that beating the $O(\sqrt{\log n})$ approximation factor of the ARV algorithm may be hard. On the other side of the coin, searching for better approximation algorithms for sparsest cut is an ostensible approach to developing algorithms for related problems, including small-set expansion and unique games.

Given the above situation, researchers have attempted to pair interesting instances with interesting algorithms to determine when constant-factor approximation to sparsest cut is possible. Below we summarize the most relevant algorithmic approaches and what is known about them.

Fiedler’s Algorithm

The simplest algorithm for sparsest cut is Fiedler’s Algorithm, which is just to threshold the second eigenvector [17]. Fiedler’s Algorithm always finds a cut $Q$ such that $\phi(G)\leqslant\sqrt{2\lambda_{2}}$ , where $\lambda_{2}$ is the second-smallest eigenvalue of the normalized Laplacian of $G$ . Indeed, this performance guarantee for Fiedler’s Algorithm is the proof of the right-hand side of Cheeger’s Inequality, which says:

\frac{\lambda_{2}}{2}\leqslant\phi(G)\leqslant\sqrt{2\lambda_{2}}\,.

This analysis of Fiedler’s algorithm shows that it gives an $O(\sqrt{\lambda_{2}}/\phi(G))$ worst-case approximation ratio, which can be quite large. Indeed, examples show, however, that the approximation factor achieved by Fiedler’s Algorithm can be as bad as $\Omega(n^{1/3})$ in general [20].

Expander-like graphs

Starting around 15 years ago, a series of works gave approximation algorithms for sparsest cut and unique games on graphs that are similar to expanders. A constant-factor approximation to sparsest cut is trivial on actual expanders (every cut is a constant-factor approximation since $\psi(G)=\Omega(1)$ ), but it took a nontrivial work of Arora et al. [4] to approximate unique games on expanders. This in turn led to efficient algorithms for sparsest cut on graphs that are “expander-like” in the sense of having few small eigenvalues, as captured by the following definition:

Definition 2 ( $\tau$ -threshold-rank).

For a graph $G$ and $2\geqslant\tau\geqslant 0\,,$ the $\tau$ -threshold-rank $\textsc{mul}_{\tau}(G)$ is the number of eigenvalues of the normalized Laplacian with value at most $\tau$ .

Recall that $G$ is an expander if and only if $\lambda_{2}$ is bounded away from 0. Equivalently, there is a constant $\tau>0$ (independent of $n$ ) such that $\textsc{mul}_{\tau}(G)=1$ . For every constant $\tau>0$ , the works [3, 10] give a constant-factor approximation algorithm for sparsest cut that runs in time polynomial in $n$ but exponential in $\textsc{mul}_{\tau}(G)$ . The algorithm of Barak, Raghavendra, and Steurer [10] is based on a rounding of a semidefinite programming relaxation, the $O(\textsc{mul}_{\tau}(G))$ ’th level of the Sum-of-Squares hierarchy. Recent work has extended the Sum-of-Squares technique based on looser expansion properties, including being a small-set expander [7], coming from a high-dimensional expander [8], or having a “succinct characterization” of non-expanding sets [9].

The algorithm of Arora, Barak, and Steurer [3] is based on enumerating the subspace spanned by the first $\textsc{mul}_{\tau}(G)$ eigenvectors to find a vector that is very close to a sparse cut. Approaches like this, which utilize multiple low eigenvectors of the Laplacian matrix, are natural generalizations of Fiedler’s Algorithm, and we collectively refer to them as higher-order spectral algorithms.

Cheeger-lower-bound graphs

With a more careful use of the Sum-of-Squares hierarchy, Guruswami and Sinop [22] showed that we can replace $\textsc{mul}_{\Omega(1)}$ in the aforementioned results with $\textsc{mul}_{O(\phi(G))}$ .

Theorem 3 ([22]).

For all constants $\varepsilon>0\,$ , sparsest cut admits a $(1+\varepsilon)$ -approximation algorithm in time $n^{O(1)}\cdot\exp\{O(r)\}$ where $r$ is the $O(\phi(G)/\varepsilon)$ -threshold-rank.

When $\phi(G)$ is small, it is not clear that graphs with small $O(\phi(G))$ -threshold-rank are “expander-like” anymore. Instead, we can think of them as graphs where the lower bound of Cheeger’s Inequality ( $\lambda_{2}/2\leqslant\phi(G)$ ) is nearly tight in the sense that $G$ has few eigenvalues between $\lambda_{2}/2$ and $\phi(G)$ .

The crucial feature of this class of graphs is that they have relatively few distinct near-sparsest cuts. Indeed, the indicator vector of a set $Q$ with conductance $O(\phi(G))$ must be close to the subspace spanned by the eigenvalues of magnitude $O(\phi(G))$ . Thus if the latter subspace has dimension $r$ , all of the near-sparsest cuts can be covered by a net of size exponential in $r$ .

A similar consequence of small $O(\phi(G))$ -threshold-rank is that these graphs can be decomposed into a small number of pieces with conductance at most $O(\phi(G))$ , such as depicted in Figure 1. See full version for a simple statement and proof of this decomposition.

Refer to caption — Figure 1: A graph with three distinct sparse cuts. In this graph, the 0/1 indicator vectors for the three pieces approximately span the three low eigenvectors.

Cut improvement

As noted by Guruswami and Sinop [22], Theorem 3 can also be proven via a higher-order spectral algorithm, based on eigenspace enumeration plus an algorithm for the cut improvement problem.¹¹1Guruswami and Sinop also study the non-uniform sparsest cut problem, which is not covered by the results on cut improvement. Informally, cut improvement is the problem of: given a cut $Q\subseteq V(G)$ , compute the sparsest cut that has large intersection with $Q$ . This is a problem of independent interest, with practical applications [2, 31, 18].

Andersen and Lang [2] gave a flow-based approximation algorithm for cut improvement which for our purposes can be summarized as follows.

Theorem 4 ([2]).

Let $G$ be an $n$ -vertex graph, let $0<\varepsilon<1/2$ , and let $Q^{*}\subseteq V(G)$ . There is a polynomial-time algorithm that, given $G$ and $Q\subseteq V(G),|Q|\leqslant n/2$ such that $|Q\cap Q^{*}|\geqslant(1-\varepsilon)|Q^{*}|$ , returns $\hat{Q}\subseteq V(G)$ with $0<\lvert\hat{Q}\rvert\leqslant n/2$ and $\phi(\hat{Q})\leqslant\frac{1}{1-2\varepsilon}\cdot\phi(Q^{*})$ .

With this cut improvement algorithm in hand, we can derive Theorem 3 (with a factor 2 loss in approximation factor) as follows: by enumerating the eigenspace up to eigenvalue $O(\phi(G)/\varepsilon)$ , we can obtain a cut $Q$ that is $\varepsilon$ -close to a sparsest cut $Q^{*}$ , and then we use Theorem 4 to find $\hat{Q}$ such that

\phi(\hat{Q})\leqslant(1+O(\varepsilon))\cdot\phi(Q^{*})\leqslant(1+O(% \varepsilon))\cdot 2\psi(G),

where the factor 2 loss comes from moving between conductance and density.

Buser graphs

A class of graphs which is in a sense complementary to the class of Cheeger-lower-bound graphs consists of graphs that satisfy a Buser Inequality $\phi=\Theta(\sqrt{\lambda_{2}})$ . Examples of graphs with bounded degree $d$ which satisfy this inequality are: graphs with non-negative discrete curvature [27, 39], Cayley graphs over Abelian groups [27, 40], or more generally Cayley graphs over nilpotent groups [12], or graphs satisfying strong bounds on their volume growth [11]. All these graphs satisfy $\phi(G)\geqslant\Omega(\sqrt{\lambda_{2}/d})$ where $d$ is the degree of the graph.

For solving these instances, it has been observed experimentally that spectral algorithms are less successful than flow-based algorithms based on the Leighton–Rao LP and its successors [34, 18]. For example, the computations of [31, Table 2] demonstrate that: for low-dimensional mesh graphs, Leighton–Rao succeeds while simple spectral thresholding algorithms are suboptimal, whereas the opposite is true for an “expander with a planted cut” similar to the graph in Figure 1. Based on this intuition, one might plausibly believe that this class of graphs is outside the range of techniques used for Theorem 3.

Note that the Buser Inequality $\phi(G)\geqslant\Omega(\sqrt{\lambda_{2}/d})$ implies that Fiedler’s Algorithm achieves $O(\sqrt{d})$ -approximation to sparsest cut since the conductance of the Fiedler cut is $O(\sqrt{\lambda_{2}})$ . Thus, Fiedler’s Algorithm can still achieve constant approximation ratio for constant $d$ , although the approximation ratio decays to $\Theta(\sqrt{\log n})$ for the hypercube graph (when it is perturbed slightly so that the $\{\pm 1\}$ -indicator of the Majority function becomes the unique second eigenvector).

1.1 Results

In this work:

1.

We give a simple algorithm for the cut improvement problem using a modification of the Leighton–Rao linear program [34]. This extends into a simple eigenspace enumeration algorithm for sparsest cut in the same way as [22, Section 4].
2.

We define a new complexity measure, the solution dimension SD, which determines the runtime of our eigenspace enumeration algorithm for sparsest cut. Comparing to Theorem 3, the solution dimension is no larger than the $O(\phi(G))$ -threshold-rank, but surprisingly, it can be significantly smaller. We demonstrate that this is the case for Cayley graphs over Abelian groups, which are a specific family of graphs satisfying the previously mentioned Buser Inequality. This gives us a PTAS for sparsest cut in Abelian Cayley graphs of degree $d=o(\log\log n/\log\log\log n)$ and a subexponential time $(1+\varepsilon)$ -approximation for $d=o(\log n/\log\log n)$ .
3.

To prove our upper bound on the solution dimension, we obtain several new facts about Abelian Cayley graphs. We bound the number of sparse cuts in an Abelian Cayley graph, showing that all $O(1)$ -approximate sparse cuts are $1-\varepsilon$ contained in the span of the first $d^{O(d)}$ eigenvectors. We also establish a new and tight bound of $2^{O(d)}$ on the multiplicity of $\lambda_{2}$ improving a previous bound of $2^{O(d^{2})}$ proven by Lee and Makaryachev [32] . In contrast to their proof, which is based on Kleiner’s proof of Gromov’s theorem [29], we directly show that the multiplicity of the $\lambda_{2}$ eigenvalue in any graph can be robustly upper bounded by a notion of volume growth of the graph.

We elaborate on these contributions below.

1.1.1 Cut Improvement

Our first result is a new algorithm for the cut improvement problem.

Theorem 5.

Let $G$ be a regular $n$ -vertex graph, let $0<\varepsilon<1/3$ and let $Q^{*}\subseteq V(G)$ , $|Q^{*}|\leqslant n/2$ . There is a polynomial time algorithm that, given $G$ and $Q\subseteq[n]$ such that $|Q\triangle Q^{*}|\leqslant\varepsilon^{3}|Q^{*}|\,,$ returns $\hat{Q}\subseteq[n]$ with $\psi(\hat{Q})\leqslant(1+O(\varepsilon))\cdot\psi(Q^{*})\,.$

Compared to Theorem 4 of Andersen and Lang [2], this theorem offers a $(1+\varepsilon)$ -approximation to the density $\psi(Q^{*})$ rather than to the conductance $\phi(Q^{*})$ , which will save us a factor of 2 in moving between the two. The algorithm of Andersen and Lang is based on iterative max flow computations on an augmented graph. In comparison, our algorithm seems conceptually simpler in that it uses the Leighton–Rao linear program with one extra constraint, followed by the simplest ball rounding scheme. While other algorithms have been proposed for the cut improvement problem, such as a spectral algorithm by Mahoney et al [36], we are unaware of other algorithms besides Theorems 4 and 5 that achieve $1+\varepsilon$ approximation to the nearby sparse cut.

1.1.2 Solution Dimension

Our second contribution is a new characterization of graphs for which a combination of eigenspace enumeration with an algorithm for cut improvement is an effective approach to sparsest cut. We name the parameter controlling the runtime of our spectral enumeration algorithm the solution dimension of the graph. For a subspace $S\subseteq\mathbb{R}^{n}\,,$ let $\mathbf{\Pi}_{S}\in\mathbb{R}^{n\times n}$ be the projection onto $S\,,$ let $C_{\varepsilon}(S):=\{x\in\mathbb{R}^{n}\,:\,\lVert x\rVert=1,\lVert\mathbf{% \Pi}_{S}{x}\rVert^{2}\geqslant 1-\varepsilon\}$ be the set of unit vectors near $S\,,$ and, for $Q\subseteq[n]$ , and let $\bar{\mathbf{1}}_{Q}\in\mathbb{R}^{n}$ be the projection of $\mathbf{1}_{Q}$ orthogonal to the all-1s vector.

Definition 6 (Sparsest Cut Solution Dimension).

Let $0\leqslant\varepsilon\leqslant 1\,,c\geqslant 1\,,$ let $G$ be an $n$ -vertex graph. Let $\mathbf{D}\in\mathbb{R}^{n\times n}$ be the diagonal matrix whose $i$ th entry is $\deg_{G}(i)$ . Let $\lambda_{1}\leqslant\cdots\leqslant\lambda_{n}$ be the sorted eigenvalues of the normalized Laplacian of $G$ and let $v_{1},\dots,v_{n}\in\mathbb{R}^{n}$ be the associated eigenvectors. The $(\varepsilon,c)$ - sparest cut solution dimension of $G$ , denoted by $\textup{{SD}}_{\varepsilon,c}(G)\,,$ is the smallest $k\in[n]$ such that there exists $Q\subseteq[n]$ with:

(i)

$\psi_{G}(Q)\leqslant c\cdot\psi(G)\,.$
(ii)

$\mathbf{D}^{1/2}\bar{\mathbf{1}}_{Q}/\lVert\mathbf{D}^{1/2}\bar{\mathbf{1}}_{Q% }\rVert\in C_{\varepsilon}(\textnormal{span}(v_{2},\ldots,v_{k+1}))$ .²²2Because of the centering, it does not matter whether the indicator of $Q$ is represented as a 0/1 vector or a $\pm 1$ vector, and $Q$ and $\bar{Q}$ are treated equivalently. For regular graphs, $\mathbf{D}$ can be ignored.

When $c=1$ we simply write $\textup{{SD}}_{\varepsilon}(G)\,.$

It can be shown that $\textup{{SD}}_{\varepsilon}(G)\leqslant\textsc{mul}_{\psi(G)/\varepsilon}(G)% \leqslant\textsc{mul}_{2\phi(G)/\varepsilon}(G)$ ; indeed every cut $Q$ can be approximated in the span of eigenvectors of eigenvalue at most $\psi(G)/\varepsilon$ . (See full version for a proof.) In this way, Theorem 7 strengthens Theorem 3. Surprisingly, the $\phi(G)$ -threshold-rank does not always match the solution dimension, allowing for potentially large speedups over Theorem 3. The cycle graph is perhaps the most basic example with solution dimension $O(1)$ whereas $\textsc{mul}_{\phi(G)}=\Theta(\sqrt{n})$ . Put another way, it suffices for eigenspace enumeration to find a $(1-\varepsilon)$ fraction of a sparse cut, instead of the entire cut, which can dramatically reduce the runtime of the enumeration.

Furthermore, while $\textsc{mul}_{\psi(G)/\varepsilon}(G)$ being small implies that there are few “distinct” sparsest cuts (since all of them are $\varepsilon$ -close to a low-dimensional subspace), small solution dimension only requires that some approximate sparsest cut is close to the low eigenspace. From this perspective, understanding whether graphs with small solution dimension yet many distinct sparsest cuts exist – and what their structure might be – appears to be a potentially valuable direction for developing new algorithms for sparsest cut.

Combining Definition 6 with Theorem 5 we deduce:

Theorem 7.

For all $0\leqslant\varepsilon<1/3\,,c\geqslant 1\,,$ sparsest cut on regular graphs admits a $c\cdot(1+O(\varepsilon))$ -approximation algorithm in time $n^{O(1)}\cdot\exp\{\textup{{SD}}_{\varepsilon^{3},c}(G)\cdot O(\log 1/% \varepsilon)\}\,.$

1.1.3 Abelian Cayley Graphs

Our next contribution is to show that using the solution dimension framework gives a dramatic speedup generically for low-degree Cayley graphs over Abelian groups.

Definition 8 (Cayley Graph).

Let $\Gamma$ be a group and let $S$ be a multiset (called the set of generators) from $\Gamma$ such that the multiplicity of $x\in S$ and $-x\in S$ is the same for all $x\in\Gamma$ . The Cayley graph of $\Gamma$ generated by $S$ , denoted $\text{Cay}(\Gamma,S)$ , is the graph with vertex set $\Gamma$ and edge set $\{(v,v\cdot s):v\in\Gamma,s\in S\}$ .

Even when restricted to constant degree, Cayley graphs provide a simple way to construct graphs with interesting algebraic and geometric properties. For example, the first expander construction by Margulis is a 12-regular Cayley graph over the group $SL_{3}(\mathbb{Z}_{p})$ [37].

Constant-degree Cayley graphs over Abelian groups, and more generally nilpotent groups, are well-known in computer science and geometric group theory as non-expanding graphs which have slow mixing properties. Degree- $d$ Abelian Cayley graphs satisfy $\phi(G)\leqslant O(n^{-2/d})$ [28, 19], the Cheeger upper bound is nearly tight due to the Buser inequality $\phi(G)\geqslant\Omega(\sqrt{\lambda_{2}/d})$ [27, 40], the volume of a radius- $r$ ball is at most $O(r^{d/2})$ , and they are flat or positively curved using any of several definitions of discrete curvature [15, 27].

Trevisan posed the question of whether sparsest cut admits an $O(1)$ -approximation in polynomial time on Abelian Cayley graphs [40]. We prove that higher-order spectral algorithms can efficiently solve sparsest cut on low-degree Abelian Cayley graphs using the solution dimension framework.

Theorem 9.

Let $G=\text{Cay}(\Gamma,S)$ be a Cayley graph over an Abelian group $\Gamma,|\Gamma|=n$ with generating set $S\subseteq\Gamma,|S|=d$ . There is an algorithm that finds a set $Q\subseteq[n],|Q|\leqslant n/2$ satisfying $\psi_{G}(Q)\leqslant(1+\varepsilon)\cdot\psi(G)$ in time $n^{O(1)}\cdot\exp\{(d/\varepsilon)^{O(d)}\}\,.$

Recall that, because of the aforementioned Buser Inequality, Fiedler’s algorithm gives an $O(\sqrt{d})$ approximation algorithm on degree $d$ Abelian Cayley graphs. In contrast, Theorem 9 gives a $(1+\varepsilon)$ approximation ratio. The price is that runtime is doubly exponential in the degree $d$ . Indeed, we obtain a PTAS for degree $d=o(\log\log n/\log\log\log n)$ and a subexponential-time approximation scheme for $d=o(\log n/\log\log n)$ .

Every finite Abelian group $\Gamma$ is isomorphic to a product of cyclic groups $\Gamma\cong\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}}$ . The minimum number $k$ of cyclic factors in such a decomposition is also the minimum size of a generating set $S$ for $\Gamma$ . Thus our algorithm is useful for groups $\Gamma$ that can be decomposed into $o(\log n/\log\log n)$ cyclic factors (such as cyclic groups). Despite the fact that $\mathbb{Z}^{k}_{2}$ requires $d\geqslant k=\log n$ generators, Cayley graphs over $\mathbb{Z}^{k}_{2}$ are easy instances. The solution dimension of Cayley graphs over $\mathbb{Z}^{k}_{2}$ satisfy that $\textup{{SD}}_{\varepsilon}=1$ for every $\varepsilon>0$ .

To prove Theorem 9 from Theorem 7, we bound the solution dimension of Abelian Cayley graphs by analyzing both their sparse cuts and their low eigenvectors. The first key ingredient is a new bound on the multiplicity of eigenvalues near $\lambda_{2}$ .

Theorem 10.

Let $G=\text{Cay}(\Gamma,S)$ be a Cayley graph over an Abelian group with generating set $S\subseteq\Gamma,|S|=d$ . For every $\lambda_{2}\leqslant\tau\leqslant\tfrac{3}{2}$ ,

\textsc{mul}_{\tau}(G)\leqslant O\left(\frac{\tau}{\lambda_{2}}\right)^{30d}.

By plugging in $\tau=\lambda_{2}\,$ , we obtain a bound of $2^{O(d)}$ on the multiplicity of the $\lambda_{2}$ eigenvalue itself, which improves a previous bound of $2^{O(d^{2})}$ proven by Lee and Makaryachev [32]. Moreover, our bound is robust, in that we also bound the number of eigenvalues that are at most $\tau=c\cdot\lambda_{2}$ by $O(c)^{O(d)}$ . For $d$ equal to a multiple of $\log n$ , our bound meets the trivial upper bound $\textsc{mul}_{\lambda_{2}}\leqslant n$ . We observe that this upper bound is tight up to the constant factor in the exponent, since there exist Cayley graphs over $\mathbb{Z}^{k}_{2}$ coming from linear error-correcting codes which have $d=O(\log n)$ and eigenvalue multiplicity $n^{\Omega(1)}$ . See the full version for the details.

Theorem 10 may be of independent interest in spectral graph theory, due in part to a recent work by Jiang et al. which resolved a longstanding open question in geometry about the maximum number of equiangular lines in $\mathbb{R}^{d}$ , using a key insight that the maximum multiplicity of $\lambda_{2}$ in a graph with maximum degree $d$ is $o_{d}(n)$ [23, 38, 24]. These works also mention Cayley graphs as useful special cases for analysis.

The second key ingredient behind Theorem 9 is a bound on sparse cuts in low-degree Abelian Cayley graphs, established by the following theorem.

Theorem 11.

Let $G=\text{Cay}(\Gamma,S)$ be a Cayley graph over an Abelian group $\Gamma,|\Gamma|=n$ with generating set $S\subseteq\Gamma,|S|=d$ . Then $\textup{{SD}}_{\varepsilon}(G)\leqslant\textsc{mul}_{\tau}(G)$ for $\tau=O(d\cdot\phi^{2}(G)/\varepsilon^{2})\,.$

Combining Theorem 10 and Theorem 11 with the Cheeger inequality $\phi^{2}(G)\leqslant O(\lambda_{2})$ returns the bound $\textup{{SD}}_{\varepsilon}(G)\leqslant(d/\varepsilon^{2})^{O(d)}\,$ on the solution dimension. This implies the final result in Theorem 9. When $d\cdot\phi^{2}(G)\ll\phi(G)$ this theorem can lead to a large gap between $\textup{{SD}}_{\varepsilon}(G)$ and $\textsc{mul}_{\phi(G)}$ and consequently to the large speedup we observe over Theorem 3.

In fact, our proof shows a stronger result that all of the sparsest cuts are $(1-\varepsilon)$ -contained in the span of the first $d^{O(d)}$ eigenvectors. That is, all of the sparsest cuts are $(1-\varepsilon)$ -close to a hyperplane cut in the $d^{O(d)}$ dimensional spectral embedding of $G$ . This upper bound on the number of sparse cuts is likely of independent interest. In particular, a line of recent work [7, 9] shows how to solve unique games instances over graphs with “certifiable” upper bounds on the number of solutions. We consider it likely that our results can therefore be extended to solve unique games instances in polynomial time on constant-degree Abelian Cayley graphs.³³3Bafna and Minzer [9] informally define a “globally hypercontractive graph” to be one with a succinct and algorithmic characterization of its small non-expanding sets. Our result informally shows that low-degree Abelian Cayley graphs have this property, although the formal definitions do not exactly meet.

Regarding Cayley graphs of larger degree, $d=\Omega(\log n)$ appears to be a natural threshold for our analysis. Indeed, all Abelian Cayley graphs with $o(\log n)$ generators have $o(1)$ expansion by the bound $\phi(G)\leqslant O(n^{-2/d})$ , whereas a random Abelian Cayley graph with $2\log n$ generators will be an expander with high probability [1]. Notably, Cayley graphs over $\mathbb{Z}_{p}^{k}$ with $p=O(1)\,,$ which may have small solution dimension, fall outside the range of structural results above, since they necessarily have $d\geqslant\Omega(\log n)$ in order to be connected. Nonetheless, Cayley graphs over $\mathbb{Z}_{p}^{k}$ in fact admit an $O(p)$ -approximation algorithm to sparsest cut. This follows from [30], but we give a simpler algorithm in the full version.

In light of the results above, we conjecture that the class of Abelian Cayley graphs does not contain hard examples for sparsest cut:

Conjecture 12.

Let $G=\text{Cay}(\Gamma,S)$ be a Cayley graph over an Abelian group $\Gamma$ of size $n$ . There is an algorithm that finds a set $Q\subseteq[n],|Q|\leqslant n/2$ satisfying $\phi_{G}(Q)\leqslant O(\phi(G))$ in time $n^{O(1)}$ .

A subexponential time algorithm would already be an interesting result, considering that there is a subexponential time algorithm for unique games [3], but efforts to lift this algorithm back to sparsest cut have not yet succeeded.

2 Techniques

We present here the main ideas behind our results. Details and proofs are mostly deferred to the full version, except for the proofs of Theorem 10 and Theorem 11, which we present in Sections 4 and 5, respectively.

Cut improvement (Theorem 5) and eigenspace enumeration (Theorem 7)

The starting point for Theorem 5 is the natural LP relaxation for sparsest cut studied in [34]. This LP relaxation assigns lengths to edges such that the average distance between all pairs of vertices is fixed, while the average edge length is minimized. The pairwise distances are constrained to form an $n$ -point semi-metric $d(\cdot,\cdot)\,:V(G)\times V(G)\to\mathbb{R}\,$ . The rounding procedure then computes a randomized line embedding $f:V(G)\to\mathbb{R}$ that is $1$ -Lipschitz and has small average distortion with respect to this metric:

\displaystyle\Omega(1/\log n)\sum_{{ij}\in V(G)}d(i,j)\leqslant\sum_{{ij}\in V% (G)}\lvert f(i)-f(j)\rvert\leqslant\sum_{{ij}\in V(G)}d(i,j)\,.

Finally, the line embedding can be easily converted into a cut, yielding a cut with sparsity at most $O(\log n)\cdot\psi(G)\,.$ The improvement of [5] comes from the fact that their program returns a metric of negative type and, for such metrics, one can efficiently construct a $1$ -Lipschitz line embedding with average distortion at most $O(\sqrt{\log n})\,.$ Hence, natural paths to improve over these results may require better constructions of the metric and the line embedding, which appears challenging and may be computationally hard in general [42].

Our key insight is that, if we enforce solutions to be close to a given partition $(Q,V(G)\setminus Q)$ in the sense that:

\displaystyle\sum_{{ij}\in Q}d(i,j)+\sum_{{ij}\notin Q}d(i,j)\leqslant% \varepsilon|Q|\cdot|V(G)\setminus Q|\,,

(1)

then any feasible metric must have two “well-separated” sets of size at least $(1-\varepsilon^{\Omega(1)})|Q|$ and $(1-\varepsilon^{\Omega(1)})|V(G)\setminus Q|$ which are at distance at least $1-\varepsilon^{\Omega(1)}\,.$ Any such feasible metric admits an efficiently computable line embedding with distortion at most $1+\varepsilon^{\Omega(1)}$ which can then be easily rounded into an integral solution. In this approach, all feasible solutions must have large overlap with $(Q,V(G)\setminus Q)$ and hence the overall quality of the output depends on the starting point $Q$ .

Finally, to obtain Theorem 7, we simply initialize the program at a good $Q$ , by finding in time $\exp\{\textup{{SD}}_{\varepsilon}(G)\}$ a partition $(Q,V(G)\setminus Q)$ that differs from a sparsest cut in at most an $\varepsilon$ -fraction of the vertices. For this choice of the constraint Equation 1 we can simultaneously ensure that the returned metric is easily roundable and that there is a nearby optimal integral solution which we $(1+\varepsilon^{\Omega(1)})$ -approximate.

Eigenvalue multiplicity (Theorem 10) and slow decay of collision probability

The common approach to bounding the eigenvalue multiplicity of graph Laplacians boils down to relating the local volume growth of induced subgraphs with the spectrum of the whole graph [23, 32, 38]. We remark that weaker bounds are also immediate consequences of higher order Cheeger inequalities [35, 33].

Limiting our discussion to $\textsc{mul}_{\lambda_{2}}(G)\,,$ in the context of Abelian Cayley graphs the most relevant work is by Lee and Makarychev [32]. Their notion of volume growth is the doubling constant: $\gamma_{G}:=\max_{t\geqslant 0}|B(2t)|/|B(t)|$ , where $B(t)$ is the ball of radius $t$ about the identity element of $\Gamma$ . By vertex transitivity the choice of the center of the ball is inconsequential. The importance of the doubling constant stems from the observation that it can be used to bound the packing number $\mathcal{N}(t)$ of the graph $G\,.$ Building on a series of existing results [14, 29, 21], Lee and Makarychev use this observation to establish

\displaystyle\textsc{mul}_{\lambda_{2}}(G)\leqslant\mathcal{N}\left(1/(\gamma_% {G}^{O(1)}\cdot\sqrt{\lambda_{2}})\right)\leqslant\gamma_{G}^{O(\log\gamma_{G}% )}\,,

where the second step leveraged the inequality $\lambda_{2}\leqslant O(\log(\gamma_{G})/\operatorname{diam}(G))^{2}\,.$ Because Abelian Cayley graphs are known to have polynomial growth $\gamma_{G}\leqslant 2^{O(d)}$ [16], this allows them to conclude $\textsc{mul}_{\lambda_{2}}(G)\leqslant 2^{O(d^{2})}\,.$

We take a much more direct (and arguably significantly simpler) approach which directly relates spectral and combinatorial quantities. The starting point is the notion of $t$ -step collision probability $\textup{{cp}}_{t}\,.$ The $t$ -step collision probability equals the probability that two independent walks of length $t$ have the same endpoint when starting from the same vertex, sampled from the stationary distribution of $G$ .⁴⁴4A technical detail is that our analysis uses lazy random walks. Thus $1/\textup{{cp}}_{t}$ serves as a probabilistic analog of the size of the ball $B(t)$ (a similar notion was also used in [38]). This motivates us to consider the following “smooth” version of the doubling constant:

\gamma^{CP}_{G}=\max_{t\geqslant 0}\frac{\textup{{cp}}_{t}}{\textup{{cp}}_{2t}}.

An important fact is that for $d$ -regular graphs the collision probability equals the average of the eigenvalues of the adjacency matrix of $G^{2t}\,,$ the ${2t}$ -th power of our starting graph. That is, we have for $t\geqslant 0\,,$

\displaystyle\textup{{cp}}_{t}=\tfrac{1}{n}\sum_{i=1}^{n}(1-\lambda_{i})^{2t}\,.

(2)

This is the $2t$ -th norm of the eigenvalues, also called the $2t$ -th Schatten norm of the adjacency matrix of $G\,.$ The crucial consequence of the expressiveness of Equation 2 is that the collision probability ratio is then entirely captured by the spectrum of $G\,:$

\displaystyle\frac{\textup{{cp}}_{t}}{\textup{{cp}}_{2t}}=\frac{\sum_{i=1}^{n}% (1-\lambda_{i})^{2t}}{\sum_{i=1}^{n}(1-\lambda_{i})^{4t}}\,.

(3)

And now the key insight is that for an appropriate choice of $t=\Theta(\log\textsc{mul}_{\lambda_{2}}(G)/\lambda_{2})\,,$ Equation 3 relates the collision probability ratio, the multiplicity of $\lambda_{2}$ and the eigenvalues of $G\,:$

\displaystyle\textsc{mul}_{\lambda_{2}}(G)^{\Omega(1)}\leqslant\frac{\textup{{% cp}}_{t}}{\textup{{cp}}_{2t}}\leqslant\gamma^{CP}_{G}\,.

The observation that, by taking longer random walks, we can learn critical information about the spectrum and avoid constructing a large packing, is the fundamental improvement over [32]. Our inequality is valid for all regular graphs and hence immediately implies a bound on the eigenvalue multiplicities for all graphs that satisfy a bound on the collision probability ratio.

Our second key contribution is an upper bound on $\gamma^{CP}_{G}$ for all Abelian Cayley graphs. To prove this statement, our challenge is to relate walks (not balls) of length $t$ to those of length $2t$ in an Abelian Cayley graph. First, we can see that in an Abelian Cayley graph, the endpoint of a walk is completely determined by how many times each generator is chosen, and not on their order. Therefore, we may replace the random walk by a random draw from a multinomial distribution, using $t$ samples of $d$ items each occurring with probability $1/d$ .

From here we can directly relate the multinomial density for $t$ to that of $2t$ . The binomial density for $2t$ samples is approximately a Gaussian $X$ with twice the variance of the density of a Gaussian $Y$ for $t$ samples, leading to a direct comparison inequality on the probability density functions, $p_{X}(x)\leqslant 2p_{Y}(x)$ for all $x\in\mathbb{R}$ . For $d$ generators, this idea can be extended (with additional arguments) to obtain a comparison equality with factor $2^{O(d)}$ which then implies

\displaystyle\textsc{mul}_{\lambda_{2}}(G)^{\Omega(1)}\leqslant\gamma^{CP}_{G}% \leqslant 2^{O(d)}\,.

(4)

The bound in Equation 4 is best possible up to the constant in the exponent: there exist Abelian Cayley graphs $\text{Cay}(\mathbb{Z}^{k}_{2},S)$ with $\textsc{mul}_{\lambda_{2}}\geqslant 2^{\Omega(d)}$ . The construction of such graphs comes from a characterization of eigenvalue multiplicity in Cayley graphs over $\mathbb{Z}^{k}_{2}$ in terms of binary linear codes. Every Cayley graph $\text{Cay}(\mathbb{Z}^{k}_{2},S)$ corresponds to a binary linear code of dimension $k$ and block length $|S|=d$ with the multiplicity of $\lambda_{2}$ corresponding to the number of code words of minimum weight. Thus, the problem of constructing Abelian Cayley graphs with large eigenvalue multiplicity is equivalent to constructing binary linear codes with many code words of minimum weight. Using algebraic geometry codes, Ashikhmin, Barg, Vlădut̨ [6] constructed a family of binary linear codes with linear rate and distance, and with an exponential number of minimum-weight codewords, which furnishes the desired construction.

Sparse cuts are approximately low-dimensional (Theorem 11)

To show that a partition $(Q,V(G)\setminus Q)$ in a graph $G$ approximately lives in the span of the first few eigenvectors, we observe that it suffices to relate its conductance in $G$ with its conductance in $G^{2t}$ in the sense:

\displaystyle\phi_{G^{2t}}(Q)\leqslant\sqrt{t}\cdot\ell\cdot\phi_{G}(Q),

(5)

for some sufficiently large $t>0$ and small $\ell>0\,.$ Recall now that the expansion can be expressed spectrally as the Rayleigh quotient of the vector $\mathbf{1}_{Q}$ . Let $\mathbf{1}_{Q}=\sum_{i\geqslant 1}q_{i}v_{i}$ be the representation of the indicator vector of the set $Q$ in the eigenbasis $v_{1},\ldots,v_{n}$ of the graph. Then the above argument implies

\displaystyle\tfrac{1}{|Q|}\sum_{i=1}^{n}q_{i}^{2}\cdot(1-(1-\lambda_{i})^{2t}% )\leqslant\sqrt{t}\cdot\ell\cdot\phi_{G}(Q)\,.

From this inequality, simple manipulations show that with the choice $t=\Theta(\varepsilon^{2}\ell^{-1}\phi^{-2})$ all but $\varepsilon$ of the spectral mass of $\bar{\mathbf{1}}_{Q}$ must be contained on eigenvalues up to $1/t$ .

To establish a version of Equation 5 for Abelian Cayley graphs, we leverage the analysis of Buser inequality [27, 40]. The proof by Oveis Gharan and Trevisan [40] studies the probability of a length- $2t$ random walk $X_{0},\ldots,X_{2t}$ crossing an arbitrary cut $Q$ . This measures the expansion of $Q$ in the graph $G^{2t}$ and their combinatorial analysis proves that Equation 5 holds for $\ell=\Theta(\sqrt{d})\,.$ As before, the crucial property of Abelian Cayley graphs being used is that it suffices to count how many times each generator is used by the walk. In the proof of this inequality, it is also important that generators $g$ and $-g$ cancel out, which allows us to bound the expected number of steps in the direction of generator $g$ by only $O(\sqrt{t/d})$ . Finally, because this argument does not rely on the specific cut $Q\,,$ we immediately obtain that for Abelian Cayley graphs, all sparsest cut approximately live in the span of the first $O(\phi^{2}\cdot d/\varepsilon^{2})$ eigenvectors.

3 Preliminaries

We establish the notation used throughout the paper along with some preliminary notions.

The norm $\lVert\cdot\rVert$ is the $\ell_{2}$ norm. For a subspace $S\subseteq\mathbb{R}^{n}\,,$ we denote by $\mathbf{\Pi}_{S}$ the orthogonal projection onto $S\,.$ For a set $Q\subseteq[n]$ we denote by $\mathbf{1}_{Q}\in\{0,1\}^{n}$ its indicator vector.

In this paper, we study undirected graphs which may have self-loops or multiedges, which we refer to as graphs. We always use $n$ to denote the number of vertices in a graph $G$ and we assume $V(G)=[n]$ . We denote by $\mathbf{A}(G)\in\mathbb{R}^{n\times n}$ the normalized adjacency matrix,

\mathbf{A}(G)_{ij}=\begin{cases}\tfrac{1}{\sqrt{\deg_{G}(i)\deg_{G}(j)}}&\text% { if ${ij}\in E(G)$}\\ 0&\text{ otherwise\,,}\end{cases}

where $\deg_{G}(i)$ is the degree of $i$ in $G$ (counting a self-loop as degree 1). When the graph is regular we use $d$ to denote its degree. In some of these definitions we may omit $G$ when the context is clear.

Let $\mathbf{D}(G)$ be the diagonal matrix with entries $\deg_{G}(i)$ . The normalized Laplacian of $G$ is defined as $\mathbf{L}(G)=\mathrm{I}-\mathbf{A}(G)\,.$ The eigenvalues of a graph $G$ are the eigenvalues of its normalized Laplacian $\mathbf{L}(G)$ and are denoted $0=\lambda_{1}(G)\leqslant\lambda_{2}(G)\leqslant\ldots\leqslant\lambda_{n}(G)$ to the associated eigenvectors $v_{1}(G),\ldots,v_{n}(G)$ . We use $1=\alpha_{1}(G)\geqslant\ldots\geqslant\alpha_{n}(G)$ for the eigenvalues of the normalized adjacency matrix, in descending order. Note that for all $i\in[n]$ , $\alpha_{i}(G)=1-\lambda_{i}(G)$ . When $G$ is regular, $\mathbf{A}(G)$ equals $\mathbf{W}(G)$ which denotes the transition matrix of the simple random walk on $G$ . When $G$ is not regular, $\mathbf{A}(G)$ and $\mathbf{W}(G)$ are similar (under conjugation by $\mathbf{D}^{1/2}$ ) so they still have the same eigenvalues.

For a set $Q\subseteq V(G)$ we let $\partial Q=\{(i,j)\in E(G):i\in Q,j\notin Q\}\,$ . For $t\in\mathbb{N}$ we denote by $G^{t}$ the multi-graph obtained by taking an edge for each length- $t$ walk in $G$ . In other words, $\mathbf{A}(G^{t})=\mathbf{A}(G)^{t}$ .

Fact 13.

For all graphs $G$ , $\mathbf{L}(G)$ is a symmetric positive semidefinite (PSD) matrix with all eigenvalues in the range $[0,2]$ .

Fact 14.

Let $\mathbf{M}\in\mathbb{R}^{n\times n}$ . If $\lambda$ is an eigenvalue of $\mathbf{M}$ , then $\lambda^{t}$ is an eigenvalue of $\mathbf{M}^{t}\,.$ Furthermore, if $\mathbf{M}\succeq 0$ then for any $i\in[n]\,,$ $\lambda_{i}(\mathbf{M}^{t})=\lambda_{i}(\mathbf{M})^{t}\,.$

An immediate corollary is the following relation between the spectrum of $G$ and its powers.

Fact 15.

Let $G$ be a graph and let $t\in\mathbb{N}\,.$ For any $i\in[n]$ it holds

\displaystyle\lambda_{i}(G^{t})=1-\left(1-\lambda_{i}(G)\right)^{t}\,.

We will make use of the following definition for the span of eigenvectors associated with small eigenvalues of the Laplacian.

Definition 16 (low eigenspace).

For a graph $G$ and $0\leqslant\tau\leqslant 2$ we define $\textnormal{{low}}_{\tau}(G)$ to be the span of the eigenvectors of $G$ associated with eigenvalues $\lambda\leqslant\tau\,.$ Notice that $\textsc{mul}_{\tau}(G)=\dim(\textnormal{{low}}_{\tau}(G))\,.$

The conductance and normalized density of a cut are defined for general graphs as follows.

Definition 17 (Conductance and density).

Let $G$ be a graph and let $Q\subseteq V(G)$ . The conductance $\phi_{G}(Q)$ and the (normalized) density $\psi_{G}(Q)$ are:

\displaystyle\phi_{G}(Q):=\frac{\lvert\partial Q\rvert}{\operatorname{vol}(Q)}% \qquad\qquad\psi_{G}(Q):=\frac{|E(Q,\bar{Q})|/|E(G)|}{2\left(\frac{% \operatorname{vol}(Q)}{\operatorname{vol}(G)}\right)\left(\frac{\operatorname{% vol}(\bar{Q})}{\operatorname{vol}(G)}\right)}

where the volume of $Q\subseteq V(G)$ is $\operatorname{vol}(Q)=\sum_{i\in Q}\deg_{G}(i)$ . The conductance and density of $G$ are then $\phi(G):=\min_{Q\subseteq V:\operatorname{vol}(Q)\leqslant\operatorname{vol}(G% )/2}\phi_{G}(Q)$ and $\psi(G):=\min_{Q\subseteq V}\psi_{G}(Q)$ .

The denominator of $\psi_{G}(Q)$ is the probability that two independent random vertices chosen according to the stationary distribution cross the $(Q,\bar{Q})$ cut, and the numerator is the probability that a random edge in the graph crosses the $(Q,\bar{Q})$ cut. Although $\partial Q$ and $E(Q,\bar{Q})$ are the same, we use both notations to highlight that $\psi_{G}(Q)$ is symmetric with respect to complementing $Q$ whereas $\phi_{G}(Q)$ is not.

Fact 18.

Let $G$ be a graph and $Q\subseteq[n]\,,\operatorname{vol}(Q)\leqslant\operatorname{vol}(G)/2\,$ . Then,

\displaystyle\phi_{G}(Q)\leqslant\psi_{G}(Q)\leqslant 2\phi_{G}(Q)\,.

These combinatorial quantities can be interpreted spectrally as simple Rayleigh quotients. For a vector $x\in\mathbb{R}^{n}$ , let $\bar{x}:=x-\left\langle x,\mathbf{1}\right\rangle/n\cdot\mathbf{1}$ denote the projection of $x$ orthogonal to the all-1s vector.

Fact 19.

Let $G$ be a graph. For all $Q\subseteq[n]$ ,

	$\displaystyle\phi_{G}(Q)$	$\displaystyle=\frac{\mathbf{1}_{Q}^{T}\mathbf{D}^{1/2}\mathbf{L}(G)\mathbf{D}^% {1/2}\mathbf{1}_{Q}}{\mathbf{1}_{Q}^{T}\mathbf{D}\mathbf{1}_{Q}}\qquad\left(% \quad=\frac{\mathbf{1}_{Q}^{T}\mathbf{L}(G)\mathbf{1}_{Q}}{\mathbf{1}_{Q}^{T}% \mathbf{1}_{Q}}\qquad\text{if $G$ is regular}\right)\,,$
	$\displaystyle\psi_{G}(Q)$	$\displaystyle=\frac{\bar{\mathbf{1}}_{Q}^{T}\mathbf{D}^{1/2}\mathbf{L}(G)% \mathbf{D}^{1/2}\bar{\mathbf{1}}_{Q}}{\bar{\mathbf{1}}_{Q}^{T}\mathbf{D}\bar{% \mathbf{1}}_{Q}}\qquad\left(\quad=\frac{\bar{\mathbf{1}}_{Q}^{T}\mathbf{L}(G)% \bar{\mathbf{1}}_{Q}}{\bar{\mathbf{1}}_{Q}^{T}\bar{\mathbf{1}}_{Q}}\qquad\text% {if $G$ is regular}\right)\,.$

Cheeger’s inequality provides a quantitative relation between eigenvalues and conductance.

Theorem 20 (Cheeger inequality).

Let $G$ be a graph. Then $\frac{\lambda_{2}}{2}\leqslant\phi(G)\leqslant\sqrt{2\lambda_{2}}\,.$

We will make use of Stirling’s approximation:

Fact 21 (Stirling’s approximation [43]).

$2\sqrt{t}\left(\frac{t}{e}\right)^{t}\leqslant t!\leqslant 2\sqrt{2t}\left(% \frac{t}{e}\right)^{t}$ for all $t\in\mathbb{N}\setminus\{0\}$ .

4 The low eigenspace of Abelian Cayley graphs

In this section, we study the low eigenspace of Abelian Cayley graphs and prove Theorem 10. We do so by analyzing the collision probability of a random walk in $G$ . For a probability distribution $\pi$ , the collision probability of $\pi$ is defined by $\textup{{cp}}(\pi)=\|\pi\|^{2}_{2}=\mathbb{P}_{x,x^{\prime}\sim\pi}(x=x^{% \prime})\,.$

Definition 22 ( $t$ -step lazy collision probability).

Let $G$ be a graph and $\pi$ be the stationary distribution for $\frac{1}{2}\mathrm{I}+\frac{1}{2}\mathbf{W}$ . The $t$ -step lazy collision probability is defined by $\textup{{cp}}_{t}=\operatorname*{\mathbb{E}}_{x\sim\pi}\textup{{cp}}\left(% \left(\frac{1}{2}\mathrm{I}+\frac{1}{2}\mathbf{W}\right)^{t}\mathbf{1}_{x}\right)$ .

Recall that the stationary distribution is proportional to the degree, and is the uniform distribution when the graph is regular. Note that for vertex-transitive graphs such as Abelian Cayley graphs, the collision probability satisfies $\textup{{cp}}_{t}=\textup{{cp}}((\frac{1}{2}\mathrm{I}+\frac{1}{2}\mathbf{W})^% {t}\mathbf{1}_{x})$ for all vertices $x$ . The next Lemma gives a spectral interpretation of $\textup{{cp}}_{t}$ as the power sums of the eigenvalues of the normalized adjacency matrix (a.k.a the moments of the empirical spectral distribution).

Lemma 23.

Let $G$ be a regular graph. Then

\textup{{cp}}_{t}=\frac{1}{n}\sum_{i=1}^{n}\left(1-\frac{\lambda_{i}}{2}\right% )^{2t}.

Proof.

Let $X_{0},X_{1},\dots,X_{2t}$ be a simple random walk initialized at $X_{0}$ drawn from the stationary distribution. Let $\tilde{X}_{0},\dots,\tilde{X}_{t}$ be an independent simple random walk initialized at $X_{0}$ . Since the simple random walk is a reversible Markov chain, $\textup{{cp}}_{t}=\operatorname*{\mathbb{P}}(X_{t}=\tilde{X}_{t})=% \operatorname*{\mathbb{P}}(X_{2t}=X_{0})$ . On the other hand, the diagonal elements of the transition matrix equal the returning probabilities of a random walk. Therefore

\displaystyle\textup{{cp}}_{t}=\operatorname*{\mathbb{E}}_{x\sim\pi}\left(% \tfrac{1}{2}\mathrm{I}+\tfrac{1}{2}\mathbf{W}\right)^{2t}_{x,x}=\frac{1}{n}% \operatorname{Tr}\left(\left(\tfrac{1}{2}\mathrm{I}+\tfrac{1}{2}\mathbf{W}% \right)^{2t}\right)=\frac{1}{n}\sum_{i=1}^{n}\left(1-\frac{\lambda_{i}}{2}% \right)^{2t},

as desired. $\hfill\blacktriangleleft$

To bound the multiplicity of eigenvalues close to $\lambda_{2}$ , we analyze the ratio $\textup{{cp}}_{t}/\textup{{cp}}_{t(\kappa+1)}$ where $t\in\mathbb{N}$ and $\kappa\geqslant 1$ are parameters. Concretely, Theorem 10 will follow from a combination of the next two statements.

The first shows that the collision probability ratio $\textup{{cp}}_{t}/\textup{{cp}}_{t(\kappa+1)}$ can be used to bound the dimension of $\textnormal{{low}}_{\tau}$ , which is equal to $\textsc{mul}_{\tau}$ , using an appropriate choice of $t$ and $\kappa$ . Interestingly, the argument works for regular graphs and not only for Abelian Cayley graphs.

Lemma 24.

Let $G$ be a connected regular graph on $n$ vertices. Suppose $\lambda_{2}\leqslant\tau\leqslant\frac{3}{2}$ and let $\kappa=\lceil\tau/\lambda_{2}\rceil$ . Then for $t=\lfloor\ln(\textsc{mul}_{\tau})/3\tau\rfloor$ , we have

\displaystyle\frac{\textup{{cp}}_{t}}{\textup{{cp}}_{t(\kappa+1)}}\geqslant% \textsc{mul}_{\tau}^{1/3}/(2e^{3/2})\,.

Proof.

First notice that for any $i\geqslant 2\,,$ it holds $0\leqslant(1-\lambda_{i}/2)\leqslant(1-\lambda_{2}/2)$ since $\lambda_{2}\leqslant\lambda_{i}\leqslant 2\,.$ By applying Lemma 23, we have

\frac{\textup{{cp}}_{t}}{\textup{{cp}}_{t(\kappa+1)}}=\frac{\sum_{i\in[n]}(1-% \lambda_{i}/2)^{2t}}{\sum_{i\in[n]}(1-\lambda_{i}/2)^{2t(\kappa+1)}}=\frac{% \sum_{i\in[n]}(1-\lambda_{i}/2)^{2t}}{1+\sum_{i\geqslant 2}(1-\lambda_{i}/2)^{% 2t(\kappa+1)}}.

We show the following lower bound,

\sum_{i\in[n]}(1-\lambda_{i}/2)^{2t}\geqslant\max\left(\textsc{mul}_{\tau}% \cdot e^{-2t\tau},e^{t\tau}\sum_{i\geqslant 2}(1-\lambda_{i}/2)^{2t(\kappa+1)}% \right).

(6)

First observe that if $\lambda_{i}\leqslant\tau$ , then $(1-\lambda_{i}/2)^{2t}\geqslant(1-\tau/2)^{2t}$ . Now by ignoring all $\lambda_{i}$ that are not in $\textnormal{{low}}_{\tau}$ , we have

	$\displaystyle\sum_{i\in[n]}(1-\lambda_{i}/2)^{2t}$	$\displaystyle\geqslant\textsc{mul}_{\tau}\cdot(1-\tau/2)^{2t}$
		$\displaystyle\geqslant\textsc{mul}_{\tau}\cdot e^{-2t\tau},$

where the last inequality uses the fact that $1-x/2\geqslant e^{-x}$ for $x\in\left[0,3/2\right]$ . Now, note that

(1-\lambda_{i}/2)^{2t}=(1-\lambda_{i}/2)^{-2t\kappa}\cdot(1-\lambda_{i}/2)^{2t% (\kappa+1)}.

This implies, $(1-\lambda_{i}/2)^{2t}\geqslant(1-\lambda_{2}/2)^{-2t\kappa}\cdot(1-\lambda_{i% }/2)^{2t(\kappa+1)}$ . In particular, we can use this to obtain

	$\displaystyle\sum_{i\in[n]}(1-\lambda_{i}/2)^{2t}$	$\displaystyle\geqslant(1-\lambda_{2}/2)^{-2t\kappa}\cdot\sum_{i\geqslant 2}(1-% \lambda_{i}/2)^{2t(\kappa+1)}$
		$\displaystyle\geqslant e^{t\tau}\cdot\sum_{i\geqslant 2}(1-\lambda_{i}/2)^{2t(% \kappa+1)}.$

The final inequality uses the fact that $1-x\leqslant e^{-x}$ and $\lambda_{2}\kappa\geqslant\tau$ . This proves (6). Observe, that for all non-negative numbers $a, b, c, d$ with $c,d>0$ we have $\max\{a,b\}/(c+d)\geqslant\frac{1}{2}\min\{a/c,b/d\}.$ This implies the following inequality

\frac{\max\left(\textsc{mul}_{\tau}\cdot e^{-2t\tau},e^{t\tau}\cdot\sum_{i% \geqslant 2}(1-\lambda_{i}/2)^{2t(\kappa+1)}\right)}{1+\sum_{i\geqslant 2}(1-% \lambda_{i}/2)^{2t(\kappa+1)}}\geqslant\frac{1}{2}\min\left(\textsc{mul}_{\tau% }\cdot e^{-2t\tau},e^{t\tau}\right).

(7)

Choosing $t=\lfloor\ln(\textsc{mul}_{\tau})/3\tau\rfloor$ gives the desired inequality. The factor of $e^{3/2}$ in the denominator comes from the fact that $e^{\tau\lfloor\ln(\textsc{mul}_{\tau})/3\tau\rfloor}\geqslant e^{\tau\left(% \frac{1}{3\tau}\ln(\textsc{mul}_{\tau})-1\right)}\geqslant\textsc{mul}_{\tau}^% {1/3}/e^{\tau}$ and the assumption $\tau\leqslant 3/2$ . $\hfill\blacktriangleleft$

The second statement we prove, which is restricted to Abelian Cayley graphs, upper bounds the ratio $\textup{{cp}}_{t}/\textup{{cp}}_{2t}$ with a function that depends on the degree $d$ of the graph but not on $t$ or $n$ .

Lemma 25.

Let $G=\text{Cay}(\Gamma,S)$ be a degree $d$ Abelian Cayley graph. Then, for every integer $t\geqslant 0\,,$ $\frac{\textup{{cp}}_{t}}{\textup{{cp}}_{2t}}\leqslant(2e)^{4d}\,.$

Proof.

To simplify the analysis of the quantity $\textup{{cp}}_{t}$ , we

1.

replace the lazy random walk with non-lazy random walk by introducing $d$ new copies of the identity element as generators, and
2.

assume each generator occurs with even multiplicity. This can be done by making a copy of every generator. Note this does not change the random walk matrix and hence the collision probabilities are preserved.

In the above two operations we introduce $3d$ new generators ( $2d$ copies of the identity and $1$ copy of each the original generators). To simplify notation, we assume $S=\{s_{1},\ldots,s_{d}\}$ satisfies the assumptions above and replace $d$ with $4d$ in the final bound.

Let $X_{0},X_{1},\dots,X_{2t}$ be a simple random walk in $G$ initialized at the identity element, denoted 0. Because $\Gamma$ is Abelian, the position of $X_{t}$ at any time can be compressed into the count of the number of times that each generator $s_{i}$ has been used as a step, which we write as the tuple $C^{(t)}\in\mathbb{N}^{d}$ . The returning walks of length $2t$ are exactly those $c\in\mathbb{N}^{d}$ such that $\sum_{i=1}^{d}c_{i}s_{i}=0$ (in $\Gamma$ ) and $\sum_{i=1}^{d}c_{i}=2t$ (in $\mathbb{N}$ ). We have:

\displaystyle\frac{\textup{{cp}}_{t}}{\textup{{cp}}_{2t}}=\frac{\operatorname*% {\mathbb{P}}(X_{2t}=X_{0})}{\operatorname*{\mathbb{P}}(X_{4t}=X_{0})}=\frac{% \sum_{{c\in\mathbb{N}^{d}:\sum_{i=1}^{d}c_{i}s_{i}=0}}\operatorname*{\mathbb{P% }}(C^{(2t)}=c)}{\sum_{{c\in\mathbb{N}^{d}:\sum_{i=1}^{d}c_{i}s_{i}=0}}% \operatorname*{\mathbb{P}}(C^{(4t)}=c)}

We define $\mu\in\mathbb{N}^{d}$ to be an integer vector whose entries are approximately $\frac{t}{d}$ .

Claim 26.

There exists $\mu\in\mathbb{N}^{d}$ such that $\sum_{i=1}^{d}\mu_{i}=2t$ , $\sum_{i=1}^{d}\mu_{i}s_{i}=0$ , and $|\mu_{i}-\mu_{j}|\leqslant 1$ for all $i,j\in[d]$ .

Let $\mu\in\mathbb{N}^{d}$ be as in the Claim. Then, by ignoring terms in the denominator except for those with $c_{i}\geqslant\mu_{i}$ for all $i$ ,

\displaystyle\frac{\sum_{{c\in\mathbb{N}^{d}:\sum_{i=1}^{d}c_{i}s_{i}=0}}% \operatorname*{\mathbb{P}}(C^{(2t)}=c)}{\sum_{{c\in\mathbb{N}^{d}:\sum_{i=1}^{% d}c_{i}s_{i}=0}}\operatorname*{\mathbb{P}}(C^{(4t)})=c)}\leqslant\frac{\sum_{{% c\in\mathbb{N}^{d}:\sum_{i=1}^{d}c_{i}s_{i}=0}}\operatorname*{\mathbb{P}}(C^{(% 2t)}=c)}{\sum_{{c\in\mathbb{N}^{d}:\sum_{i=1}^{d}c_{i}s_{i}=0}}\operatorname*{% \mathbb{P}}(C^{(4t)}=c+\mu)}\,.

The point of the inequality is that it now suffices to show the direct comparison inequality $\frac{\operatorname*{\mathbb{P}}(C^{(2t)}=c)}{\operatorname*{\mathbb{P}}(C^{(4% t)}=c+\mu)}\leqslant(2e)^{d}$ for all $c\in\mathbb{N}^{d}$ with $\sum_{i=1}^{d}c_{i}=2t$ (dropping the constraint that $\sum_{i=1}^{d}c_{i}s_{i}=0$ in $\Gamma$ ). Towards this, we have

\displaystyle\frac{\operatorname*{\mathbb{P}}(C^{(2t)}=c)}{\operatorname*{% \mathbb{P}}(C^{(4t)}=c+\mu)}=\frac{\binom{2t}{c_{1},\dots,c_{d}}d^{4t}}{\binom% {4t}{c_{1}+\mu_{1},\dots,c_{d}+\mu_{d}}d^{2t}}=\frac{(2t)!(c_{1}+\mu_{1})!% \cdots(c_{d}+\mu_{d})!d^{2t}}{(4t)!c_{1}!\cdots c_{d}!}\,.

We prove by “discrete gradient descent” that this quantity is maximized when $c=\mu$ . Let $c^{\prime}$ be $c$ with $c_{i}$ replaced by $c_{i}+1$ and $c_{j}$ replaced by $c_{j}-1$ . The ratio of the consecutive terms is,

\displaystyle\frac{\operatorname*{\mathbb{P}}(C^{(2t)}=c^{\prime})}{% \operatorname*{\mathbb{P}}(C^{(4t)})=c^{\prime}+\mu)}\cdot\frac{\operatorname*% {\mathbb{P}}(C^{(4t)}=c+\mu)}{\operatorname*{\mathbb{P}}(C^{(2t)}=c)}=\frac{(c% _{i}+\mu_{i}+1)c_{j}}{(c_{i}+1)(c_{j}+\mu_{j})}\,.

This is at least 1 if and only if $\frac{c_{j}}{c_{i}+1}\geqslant\frac{\mu_{j}}{\mu_{i}}$ . If this holds, the change $(c_{i},c_{j})\to(c_{i}+1,c_{j}-1)$ increases the value. This implies that $c=\mu$ at the maximizer (since if $c\neq\mu$ , there is at least once coordinate which is smaller than $\mu$ and one coordinate which is larger than $\mu$ in which we can move to increase the value).

Finally, we bound the value at the maximizer.

$\displaystyle\frac{\operatorname{\mathbb{P}}(C^{(2t)}=\mu)}{\operatorname{% \mathbb{P}}(C^{(4t)}=2\mu)}$	$\displaystyle=\frac{(2t)!d^{2t}\prod_{i=1}^{d}(2\mu_{i})!}{(4t)!\prod_{i=1}^{d% }\mu_{i}!}$
	$\displaystyle\leqslant 2^{d/2+1}\frac{\sqrt{2t}(2t/e)^{2t}d^{2t}\prod_{i=1}^{d% }\sqrt{2\mu_{i}}(2\mu_{i}/e)^{2\mu_{i}}}{\sqrt{4t}(4t/e)^{4t}\prod_{i=1}^{d}% \sqrt{\mu_{i}}(\mu_{i}/e)^{\mu_{i}}}$	$\displaystyle(\text{\lx@cref{creftype~refnum}{fact:stirling}})$
	$\displaystyle=2^{d}\cdot\frac{d^{2t}\prod_{i=1}^{d}2^{2\mu_{i}}\mu_{i}^{\mu_{i% }}}{2^{4t}(2t)^{2t}}$
	$\displaystyle\leqslant 2^{d}\cdot\frac{d^{2t}\prod_{i=1}^{d}2^{2\mu_{i}}(\frac% {2t}{d}+1)^{\mu_{i}}}{2^{4t}(2t)^{2t}}$	$\displaystyle(\mu_{i}\leqslant\frac{2t}{d}+1)$
	$\displaystyle=2^{d}\cdot\left(\frac{d}{2t}\right)^{2t}\left(\frac{2t}{d}+1% \right)^{2t}$	$\displaystyle\left(\sum_{i=1}^{d}\mu_{i}=2t\right)$
	$\displaystyle=2^{d}\left(1+\frac{d}{2t}\right)^{2t}\leqslant(2e)^{d}$	$\displaystyle(1+x\leqslant e^{x})\,.$

Which concludes the proof. $\hfill\blacktriangleleft$

We are now ready to prove Theorem 10.

Proof of Theorem 10.

The Theorem follows immediately combining Lemma 24 and Lemma 25. By Lemma 25, for every integer $t\geqslant 0$ we have $\textup{{cp}}_{t}/\textup{{cp}}_{2t}\leqslant(2e)^{4d}\leqslant 2^{10d}$ . Let $\kappa=\lceil\tau/\lambda_{2}\rceil.$ Observe,

	$\displaystyle\frac{\textsc{mul}_{\tau}^{1/3}}{(2e^{3/2})}\leqslant\frac{% \textup{{cp}}_{t}}{\textup{{cp}}_{{t(\kappa+1)}}}$	$\displaystyle\leqslant\frac{\textup{{cp}}_{t}}{\textup{{cp}}_{2t}}\cdot\frac{% \textup{{cp}}_{2t}}{\textup{{cp}}_{4t}}\cdots\frac{\textup{{cp}}_{t2^{\lceil% \log(\kappa+1)\rceil-1}}}{\textup{{cp}}_{t2^{\lceil\log(\kappa+1)\rceil}}}$
		$\displaystyle\leqslant 2^{10d\lceil\log(\kappa+1)\rceil}$
		$\displaystyle\leqslant 2^{10d\log(O(\tau/\lambda_{2}))},$

where the last inequality uses the fact that $\kappa\leqslant 2\tau/\lambda_{2}$ and $\log(2\tau/\lambda_{2}+1)\leqslant\log(3\tau/\lambda_{2})$ . This implies,

	$\displaystyle\textsc{mul}_{\tau}$	$\displaystyle\leqslant 2^{30d\log(O(\tau/\lambda_{2}))+11}$
		$\displaystyle\leqslant O\left(\frac{\tau}{\lambda_{2}}\right)^{30d}.\$

$\hfill\blacktriangleleft$

5 The sparse cuts of Abelian Cayley graphs

In this section, we prove that all sparse cuts of an Abelian Cayley graph are approximately contained in the low eigenspace with $\tau=O(d\cdot\phi^{2})$ thus obtaining Theorem 11.

Theorem 27.

Let $G=\text{Cay}(\Gamma,S)$ with $\left\lvert S\right\rvert=d\,.$ Let $0<\varepsilon\leqslant 1$ and $\tau=100d\cdot\phi^{2}/\varepsilon^{2}\,.$ For all $Q\subseteq[n],|Q|\leqslant n/2$ such that $\phi_{G}(Q)\leqslant 2\phi(G)\,,$ we have $\left\lVert\mathbf{\Pi}_{\textnormal{{low}}_{\tau}}\bar{\mathbf{1}}_{Q}\right% \rVert^{2}\geqslant(1-\varepsilon)\left\lVert\bar{\mathbf{1}}_{Q}\right\rVert^% {2}\,.$

The proof extends the combinatorial proof of the Buser inequality in graphs due to Oveis Gharan and Trevisan [40]. Let $Q\subseteq[n]$ be a sparsest cut in $G=\text{Cay}(\Gamma,S)$ . We analyze the expansion of $Q$ in the graph $G^{2t}$ for an appropriate choice of $t\in\mathbb{N}$ . Following the proof of the Buser inequality [40], this quantity can be bounded in terms of the expansion in $G$ .

Lemma 28 ([40]).

$\phi_{G^{2t}}(Q)\leqslant 2\sqrt{td}\cdot\phi_{G}(Q)$ .

Proof of Theorem 27.

By Fact 19 the expansion has a spectral representation,

\phi_{G^{2t}}(G)=\frac{\mathbf{1}_{Q}^{T}\mathbf{L}(G^{2t})\mathbf{1}_{Q}}{% \mathbf{1}_{Q}^{T}\mathbf{1}_{Q}}\,.

(8)

Let $\mathbf{1}_{Q}=\sum_{i=1}^{n}q_{i}v_{i}(G)$ be the representation of $\mathbf{1}_{Q}$ in the eigenbasis. The eigenvalues of $\mathbf{L}(G^{2t})$ are equal to $1-(1-\lambda_{i}(G))^{2t}$ . By combining Equation 8 and Lemma 28 we obtain,

\frac{1}{|Q|}\sum_{i=2}^{n}q_{i}^{2}(1-(1-\lambda_{i})^{2t})\leqslant 2\sqrt{% td}\cdot\phi_{G}(Q)\,.

We interpret the left-hand side probabilistically. Let $i\sim\mathcal{S}(Q)$ denote the “spectral sample” distribution on $\{2,3,\dots,n\}$ taking value $i$ with probability proportional to $q_{i}^{2}$ i.e. the weight of $\bar{\mathbf{1}}_{Q}$ on the $i$ th eigenvector. The normalizing factor for $\mathcal{S}(Q)$ is $\lVert\bar{\mathbf{1}}_{Q}\rVert^{2}=\sum_{i=2}^{n}q_{i}^{2}=\frac{|Q|(n-|Q|)}% {n}\geqslant\frac{|Q|}{2}$ using $|Q|\leqslant n/2$ . Then we have,

\operatorname*{\mathbb{E}}_{i\sim\mathcal{S}(Q)}[1-e^{-2\lambda_{i}t}]% \leqslant\operatorname*{\mathbb{E}}_{i\sim\mathcal{S}(Q)}[1-(1-\lambda_{i})^{2% t}]\leqslant 8\sqrt{td}\cdot\phi(G)

Fixing a threshold $\tau\geqslant 0$ , we upper bound $\operatorname*{\mathbb{E}}_{i\sim\mathcal{S}(Q)}[e^{-2\lambda_{i}t}]\leqslant(% 1-p)+pe^{-2\tau t}$ where $p:=1-\lVert\mathbf{\Pi}_{\textnormal{{low}}_{\tau}}\bar{\mathbf{1}}_{Q}\rVert^% {2}/\lVert\bar{\mathbf{1}}_{Q}\rVert^{2}$ is the fraction of mass outside of the low eigenspace. Therefore,

p(1-e^{-2\tau t})\leqslant 8\sqrt{td}\cdot\phi(G)\,.

Selecting $\tau=100\varepsilon^{-2}d\phi^{2}(G)$ and $t=1/\tau\,,$ we conclude $p\leqslant\varepsilon$ i.e. at least $1-\varepsilon$ fraction of the mass of $\mathbf{1}_{Q}$ is on the low eigenspace. This finishes the proof of Theorem 27. $\hfill\blacktriangleleft$

References

[1] Noga Alon and Yuval Roichman. Random cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994. doi:10.1002/RSA.3240050203.
[2] Reid Andersen and Kevin J Lang. An algorithm for improving graph partitions. In SODA, volume 8, pages 651–660, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347154.
[3] Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. Journal of the ACM (JACM), 62(5):1–25, 2015. doi:10.1145/2775105.
[4] Sanjeev Arora, Subhash A Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K Vishnoi. Unique games on expanding constraint graphs are easy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 21–28, 2008.
[5] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1–37, 2009. doi:10.1145/1502793.1502794.
[6] Alexei Ashikhmin, Alexander Barg, and Serge Vladut. Linear codes with exponentially many light vectors. Journal of combinatorial theory. Series A, 96(2):396–399, 2001. doi:10.1006/JCTA.2001.3206.
[7] Mitali Bafna, Boaz Barak, Pravesh K Kothari, Tselil Schramm, and David Steurer. Playing unique games on certified small-set expanders. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1629–1642, 2021. doi:10.1145/3406325.3451099.
[8] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett. High dimensional expanders: Eigenstripping, pseudorandomness, and unique games. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1069–1128. SIAM, 2022. doi:10.1137/1.9781611977073.47.
[9] Mitali Bafna and Dor Minzer. Solving unique games over globally hypercontractive graphs. arXiv preprint arXiv:2304.07284, 2023. doi:10.48550/arXiv.2304.07284.
[10] Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 2011 ieee 52nd annual symposium on foundations of computer science, pages 472–481. IEEE, 2011. doi:10.1109/FOCS.2011.95.
[11] Brian Benson, Peter Ralli, and Prasad Tetali. Volume growth, curvature, and buser-type inequalities in graphs. International Mathematics Research Notices, 2021(22):17091–17139, 2021.
[12] Emmanuel Breuillard and Matthew CH Tointon. Nilprogressions and groups with moderate growth. Advances in Mathematics, 289:1008–1055, 2016.
[13] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D Sivakumar. On the hardness of approximating multicut and sparsest-cut. computational complexity, 15:94–114, 2006. doi:10.1007/S00037-006-0210-9.
[14] Tobias H Colding and William P Minicozzi. Harmonic functions on manifolds. Annals of mathematics, 146(3):725–747, 1997.
[15] David Cushing, Supanat Kamtue, Riikka Kangaslampi, Shiping Liu, and Norbert Peyerimhoff. Curvatures, graph products and ricci flatness. Journal of Graph Theory, 96(4):522–553, 2021. doi:10.1002/jgt.22630.
[16] Persi Diaconis and Laurent Saloff-Coste. Moderate growth and random walk on finite groups. Geometric & Functional Analysis GAFA, 4:1–36, 1994.
[17] Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298–305, 1973.
[18] Kimon Fountoulakis, Meng Liu, David F Gleich, and Michael W Mahoney. Flow-based algorithms for improving clusters: A unifying framework, software, and performance. SIAM Review, 65(1):59–143, 2023. doi:10.1137/20M1333055.
[19] Joel Friedman, Ram Murty, and Jean-Pierre Tillich. Spectral estimates for abelian cayley graphs. Journal of Combinatorial Theory, Series B, 96(1):111–121, 2006. doi:10.1016/J.JCTB.2005.06.012.
[20] Stephen Guattery and Gary L Miller. On the quality of spectral separators. SIAM Journal on Matrix Analysis and Applications, 19(3):701–719, 1998. doi:10.1137/S0895479896312262.
[21] Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 534–543. IEEE, 2003. doi:10.1109/SFCS.2003.1238226.
[22] Venkatesan Guruswami and Ali Kemal Sinop. Approximating non-uniform sparsest cut via generalized spectra. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 295–305. SIAM, 2013. doi:10.1137/1.9781611973105.22.
[23] Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao. Equiangular lines with a fixed angle. Annals of Mathematics, 194(3):729–743, 2021.
[24] Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao. Spherical two-distance sets and eigenvalues of signed graphs. Combinatorica, 43(2):203–232, 2023. doi:10.1007/S00493-023-00002-1.
[25] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002. doi:10.1145/509907.510017.
[26] Subhash A Khot and Nisheeth K Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into $\ell$ -1. Journal of the ACM (JACM), 62(1):1–39, 2015. doi:10.1145/2629614.
[27] Bo’az Klartag, Gady Kozma, Peter Ralli, and Prasad Tetali. Discrete curvature and abelian groups. Canadian Journal of Mathematics, 68(3):655–674, 2016.
[28] Maria Klawe. Non-existence of one-dimensional expanding graphs. In 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981), pages 109–114. IEEE, 1981. doi:10.1109/SFCS.1981.23.
[29] Bruce Kleiner. A new proof of gromov’s theorem on groups of polynomial growth. Journal of the American Mathematical Society, 23(3):815–829, 2010.
[30] Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. Improved cheeger’s inequality: analysis of spectral partitioning algorithms through higher order spectral gap. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 11–20, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488611.
[31] Kevin J Lang, Michael W Mahoney, and Lorenzo Orecchia. Empirical evaluation of graph partitioning using spectral embeddings and flow. In International Symposium on Experimental Algorithms, pages 197–208. Springer, 2009. doi:10.1007/978-3-642-02011-7_19.
[32] James R Lee and Yury Makarychev. Eigenvalue multiplicity and volume growth. arXiv preprint arXiv:0806.1745, 2008.
[33] James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1–30, 2014. doi:10.1145/2665063.
[34] Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787–832, 1999. doi:10.1145/331524.331526.
[35] Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Many sparse cuts via higher eigenvalues. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1131–1140, 2012. doi:10.1145/2213977.2214079.
[36] Michael W Mahoney, Lorenzo Orecchia, and Nisheeth K Vishnoi. A spectral algorithm for improving graph partitions. Technical report, Technical report. Preprint, 2009.
[37] Grigorii Aleksandrovich Margulis. Explicit constructions of concentrators. Problemy Peredachi Informatsii, 9(4):71–80, 1973.
[38] Theo McKenzie, Peter Michael Reichstein Rasmussen, and Nikhil Srivastava. Support of closed walks and second eigenvalue multiplicity of graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 396–407, 2021. doi:10.1145/3406325.3451129.
[39] Florentin Münch. Non-negative ollivier curvature on graphs, reverse poincaré inequality, buser inequality, liouville property, harnack inequality and eigenvalue estimates. Journal de Mathématiques Pures et Appliquées, 170:231–257, 2023.
[40] Shayan Oveis Gharan and Luca Trevisan. ARV on abelian cayley graphs. In Theory blog, 2021.
[41] Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 755–764, 2010. doi:10.1145/1806689.1806792.
[42] Prasad Raghavendra, David Steurer, and Madhur Tulsiani. Reductions between expansion problems. In 2012 IEEE 27th Conference on Computational Complexity, pages 64–73. IEEE, 2012. doi:10.1109/CCC.2012.43.
[43] Wikipedia. Stirling’s approximation. https://en.wikipedia.org/wiki/Stirling%27s_approximation. Accessed: 2024-10-24.

[bib.bib1] [1] Noga Alon and Yuval Roichman. Random cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994. doi:10.1002/RSA.3240050203.

[bib.bib2] [2] Reid Andersen and Kevin J Lang. An algorithm for improving graph partitions. In SODA, volume 8, pages 651–660, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347154.

[bib.bib3] [3] Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. Journal of the ACM (JACM), 62(5):1–25, 2015. doi:10.1145/2775105.

[bib.bib4] [4] Sanjeev Arora, Subhash A Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K Vishnoi. Unique games on expanding constraint graphs are easy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 21–28, 2008.

[bib.bib5] [5] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1–37, 2009. doi:10.1145/1502793.1502794.

[bib.bib6] [6] Alexei Ashikhmin, Alexander Barg, and Serge Vladut. Linear codes with exponentially many light vectors. Journal of combinatorial theory. Series A, 96(2):396–399, 2001. doi:10.1006/JCTA.2001.3206.

[bib.bib7] [7] Mitali Bafna, Boaz Barak, Pravesh K Kothari, Tselil Schramm, and David Steurer. Playing unique games on certified small-set expanders. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1629–1642, 2021. doi:10.1145/3406325.3451099.

[bib.bib8] [8] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett. High dimensional expanders: Eigenstripping, pseudorandomness, and unique games. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1069–1128. SIAM, 2022. doi:10.1137/1.9781611977073.47.

[bib.bib9] [9] Mitali Bafna and Dor Minzer. Solving unique games over globally hypercontractive graphs. arXiv preprint arXiv:2304.07284, 2023. doi:10.48550/arXiv.2304.07284.

[bib.bib10] [10] Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 2011 ieee 52nd annual symposium on foundations of computer science, pages 472–481. IEEE, 2011. doi:10.1109/FOCS.2011.95.

[bib.bib11] [11] Brian Benson, Peter Ralli, and Prasad Tetali. Volume growth, curvature, and buser-type inequalities in graphs. International Mathematics Research Notices, 2021(22):17091–17139, 2021.

[bib.bib12] [12] Emmanuel Breuillard and Matthew CH Tointon. Nilprogressions and groups with moderate growth. Advances in Mathematics, 289:1008–1055, 2016.

[bib.bib13] [13] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D Sivakumar. On the hardness of approximating multicut and sparsest-cut. computational complexity, 15:94–114, 2006. doi:10.1007/S00037-006-0210-9.

[bib.bib14] [14] Tobias H Colding and William P Minicozzi. Harmonic functions on manifolds. Annals of mathematics, 146(3):725–747, 1997.

[bib.bib15] [15] David Cushing, Supanat Kamtue, Riikka Kangaslampi, Shiping Liu, and Norbert Peyerimhoff. Curvatures, graph products and ricci flatness. Journal of Graph Theory, 96(4):522–553, 2021. doi:10.1002/jgt.22630.

[bib.bib16] [16] Persi Diaconis and Laurent Saloff-Coste. Moderate growth and random walk on finite groups. Geometric & Functional Analysis GAFA, 4:1–36, 1994.

[bib.bib17] [17] Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298–305, 1973.

[bib.bib18] [18] Kimon Fountoulakis, Meng Liu, David F Gleich, and Michael W Mahoney. Flow-based algorithms for improving clusters: A unifying framework, software, and performance. SIAM Review, 65(1):59–143, 2023. doi:10.1137/20M1333055.

[bib.bib19] [19] Joel Friedman, Ram Murty, and Jean-Pierre Tillich. Spectral estimates for abelian cayley graphs. Journal of Combinatorial Theory, Series B, 96(1):111–121, 2006. doi:10.1016/J.JCTB.2005.06.012.

[bib.bib20] [20] Stephen Guattery and Gary L Miller. On the quality of spectral separators. SIAM Journal on Matrix Analysis and Applications, 19(3):701–719, 1998. doi:10.1137/S0895479896312262.

[bib.bib21] [21] Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 534–543. IEEE, 2003. doi:10.1109/SFCS.2003.1238226.

[bib.bib22] [22] Venkatesan Guruswami and Ali Kemal Sinop. Approximating non-uniform sparsest cut via generalized spectra. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 295–305. SIAM, 2013. doi:10.1137/1.9781611973105.22.

[bib.bib23] [23] Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao. Equiangular lines with a fixed angle. Annals of Mathematics, 194(3):729–743, 2021.

[bib.bib24] [24] Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao. Spherical two-distance sets and eigenvalues of signed graphs. Combinatorica, 43(2):203–232, 2023. doi:10.1007/S00493-023-00002-1.

[bib.bib25] [25] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002. doi:10.1145/509907.510017.

[bib.bib26] [26] Subhash A Khot and Nisheeth K Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into $\ell$ -1. Journal of the ACM (JACM), 62(1):1–39, 2015. doi:10.1145/2629614.

[bib.bib27] [27] Bo’az Klartag, Gady Kozma, Peter Ralli, and Prasad Tetali. Discrete curvature and abelian groups. Canadian Journal of Mathematics, 68(3):655–674, 2016.

[bib.bib28] [28] Maria Klawe. Non-existence of one-dimensional expanding graphs. In 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981), pages 109–114. IEEE, 1981. doi:10.1109/SFCS.1981.23.

[bib.bib29] [29] Bruce Kleiner. A new proof of gromov’s theorem on groups of polynomial growth. Journal of the American Mathematical Society, 23(3):815–829, 2010.

[bib.bib30] [30] Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. Improved cheeger’s inequality: analysis of spectral partitioning algorithms through higher order spectral gap. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 11–20, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488611.

[bib.bib31] [31] Kevin J Lang, Michael W Mahoney, and Lorenzo Orecchia. Empirical evaluation of graph partitioning using spectral embeddings and flow. In International Symposium on Experimental Algorithms, pages 197–208. Springer, 2009. doi:10.1007/978-3-642-02011-7_19.

[bib.bib32] [32] James R Lee and Yury Makarychev. Eigenvalue multiplicity and volume growth. arXiv preprint arXiv:0806.1745, 2008.

[bib.bib33] [33] James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1–30, 2014. doi:10.1145/2665063.

[bib.bib34] [34] Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787–832, 1999. doi:10.1145/331524.331526.

[bib.bib35] [35] Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Many sparse cuts via higher eigenvalues. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1131–1140, 2012. doi:10.1145/2213977.2214079.

[bib.bib36] [36] Michael W Mahoney, Lorenzo Orecchia, and Nisheeth K Vishnoi. A spectral algorithm for improving graph partitions. Technical report, Technical report. Preprint, 2009.

[bib.bib37] [37] Grigorii Aleksandrovich Margulis. Explicit constructions of concentrators. Problemy Peredachi Informatsii, 9(4):71–80, 1973.

[bib.bib38] [38] Theo McKenzie, Peter Michael Reichstein Rasmussen, and Nikhil Srivastava. Support of closed walks and second eigenvalue multiplicity of graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 396–407, 2021. doi:10.1145/3406325.3451129.

[bib.bib39] [39] Florentin Münch. Non-negative ollivier curvature on graphs, reverse poincaré inequality, buser inequality, liouville property, harnack inequality and eigenvalue estimates. Journal de Mathématiques Pures et Appliquées, 170:231–257, 2023.

[bib.bib40] [40] Shayan Oveis Gharan and Luca Trevisan. ARV on abelian cayley graphs. In Theory blog, 2021.

[bib.bib41] [41] Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 755–764, 2010. doi:10.1145/1806689.1806792.

[bib.bib42] [42] Prasad Raghavendra, David Steurer, and Madhur Tulsiani. Reductions between expansion problems. In 2012 IEEE 27th Conference on Computational Complexity, pages 64–73. IEEE, 2012. doi:10.1109/CCC.2012.43.

[bib.bib43] [43] Wikipedia. Stirling’s approximation. https://en.wikipedia.org/wiki/Stirling%27s_approximation. Accessed: 2024-10-24.

Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 (Sparsest Cut).

Fiedler’s Algorithm

Expander-like graphs

Definition 2 (τ-threshold-rank).

Cheeger-lower-bound graphs

Theorem 3 ([22]).

Cut improvement

Theorem 4 ([2]).

Buser graphs

1.1 Results

1.1.1 Cut Improvement

Theorem 5.

1.1.2 Solution Dimension

Definition 6 (Sparsest Cut Solution Dimension).

Theorem 7.

1.1.3 Abelian Cayley Graphs

Definition 8 (Cayley Graph).

Theorem 9.

Theorem 10.

Theorem 11.

Conjecture 12.

2 Techniques

Cut improvement (Theorem 5) and eigenspace enumeration (Theorem 7)

Eigenvalue multiplicity (Theorem 10) and slow decay of collision probability

Sparse cuts are approximately low-dimensional (Theorem 11)

3 Preliminaries

Fact 13.

Fact 14.

Fact 15.

Definition 16 (low eigenspace).

Definition 17 (Conductance and density).

Fact 18.

Fact 19.

Theorem 20 (Cheeger inequality).

Fact 21 (Stirling’s approximation [43]).

4 The low eigenspace of Abelian Cayley graphs

Definition 22 (t-step lazy collision probability).

Lemma 23.

Proof.

Lemma 24.

Proof.

Lemma 25.

Proof.

Claim 26.

Proof of Theorem 10.

5 The sparse cuts of Abelian Cayley graphs

Theorem 27.

Lemma 28 ([40]).

Proof of Theorem 27.

References

Definition 2 ( $\tau$ -threshold-rank).

Definition 22 ( $t$ -step lazy collision probability).