Remarks on partitions into expanders

Abstract

In this note we give a short proof that graphs having no linearly small Følner sets can be partitioned into a union of expanders. We use this fact to prove a partition result for graphs admitting linearly small maximal Følner sets and we deduce that a family of such graphs must contain a family of expanders. We also show that the existence of partitions into expanders is a quasi-isometry invariant.

1 Introduction

This paper revolves around the fact that “graphs where linearly-small subsets have large boundaries can be partitioned into unions of linearly-large expanders”. To make the statement clear, we need to introduce some terminology: let X be a finite graph with no multiple edges or loops. Given a finite set of vertices $A\subseteq X$, the boundary of A is the set of edges connecting A to its complement:

$$\begin{aligned} \partial A=\{\{v,w\}\in \text {E}(X)|v\in A,\ w\in X\smallsetminus A\}. \end{aligned}$$

Given $\epsilon >0$, a non-empty set of vertices $A\subset X$ is an $\epsilon$-Følner set if $|A|\le \frac{1}{2}|X|$ and $|\partial A|\le \epsilon |A|$ (here $|X|$ is the number of vertices in X). The graph X is an $\epsilon$-expander if it contains no $\epsilon$-Følner sets. Let $\deg (X):=\max \{\deg (v)|v\in X\}$ be the degree of X and $D\in \mathbb {N}$ some number. Then X is an $(\epsilon ,D)$-expander if it is an $\epsilon$-expander and $\deg (X)\le D$.

If X is a connected finite graph, it is trivially a $(\frac{2}{|X|},|X|)$-expander. On the other hand, it is generally hard and very interesting to prove that a graph X is an $(\epsilon ,D)$-expander for some constants $\epsilon$, D that are fixed a priori and do not depend on $|X|$. A family of expander graphs is a sequence of $(\epsilon , D)$-expanders $(X_n)_{n\in \mathbb {N}}$ such that $|X_n|\rightarrow \infty$. We refer to [6] for more background and motivation.

A subset of vertices $Y\subset X$ can be made into a subgraph of X by keeping all the edges in X with both endpoints in Y (such a graph is often called a full subgraph of X). In this paper we will say that $X=X_1\sqcup \cdots \sqcup X_n$ is a partition of X if $X_i$ are subgraphs arising from a partition of the set of vertices of X. We do not require that every edge of X is an edge of $X_i$ for some i (i.e. there might be edges connecting the $X_i$’s). We will be particularly interested in partitions where the graphs $X_i$ are $\epsilon$-expanders. If $\deg (X)\le D$, $X_i$ will then automatically be $(\epsilon ,D)$-expanders.

Finally, given a constant $\alpha \in (0,1)$ we say that a subset $A\subseteq X$ is $\alpha$-big if $|A|\ge \alpha |X|$, and that it is $\alpha$-small if $|A|<\alpha |X|$. Given nested subsets $A\subseteq Y\subseteq X$, we will avoid confusion by specifying whether A is $\alpha$-big in Y or in X (and similarly for $\alpha$-small).

In this paper we wish to give an elementary proof of the fact that graphs with a “small-set expansion on a linear scale” can be partitioned into linearly-large expanders:

Theorem A

Let X be a finite graph. If X has no $\alpha$-small $\epsilon$-Følner sets, then it can be partitioned as $X=X_1\sqcup \cdots \sqcup X_k$ where $k\le \lfloor \frac{1}{\alpha }\rfloor$, all the $X_i$ are $\alpha$-big and they are $\delta$-expanders for $\delta =\frac{\epsilon }{4^k}$.

Apart from the specific constants, Theorem A can be easily deduced from a—much more refined—result of Oveis Gharam–Trevisan [3][Theorem 1.5] (see Remark 3.3 for a more detailed comparison). The main contribution of this note is to provide a short self-contained proof for Theorem A (Sect. 3).

We hope that this work will help popularize this basic but not-so-well-known fact. For this reason, we begin our exposition by illustrating a few geometric consequences of Theorem A (Sect. 2). Namely, we prove a rather general partition result for graphs, and we also use Theorem A to show that the property of admitting partitions into linearly large expanders is invariant under quasi-isometry. We find that Theorems 2.2, 2.8 and Corollary 2.3 should be of independent interest.

It is also worth pointing out that the objects of interest of this note (expanders and Følner sets) are very much related to the notion of separation profile introduced by Benjamini–Schramm–Timár [1]. Some analogues of the techniques explained below proved to be useful in that context as well [2, 7].

2 Consequences of the main result

2.1 A general partition theorem

It is convenient to introduce a piece of notation: given subsets $A,B\subset X$, we let $\partial ^BA$ be the set of edges in X joining a vertex in A with a vertex in $B\smallsetminus A$ (this is the subset of $\partial A$ consisting of edges that land in B). It is interesting to combine Theorem A with the “maximal Følner set trick”:

Lemma 2.1

Let X be a finite graph and $\epsilon >0$ a fixed constant. If there exists an $\epsilon$-Følner set F that is maximal with respect to inclusion, consider the subgraph $Y:=X\smallsetminus F$. Then every subset $A\subset Y$ such that $|A|\le \frac{1}{2}|X|-|F|$ satisfies $|\partial ^YA|>\epsilon |A|$.

This sort of maximality argument is used fairly often in the theory of von Neumann algebras and it was also a key ingredient in [8]. The proof of Lemma 2.1 is completely elementary and can also be found in [8][Lemma 3.1]. Together with Theorem A, the maximality trick implies the following structure theorem:

Theorem 2.2

Let X be a finite graph. If X has a maximal $\epsilon$-Følner set F that is $\alpha$-small for some $\alpha <\frac{1}{2}$, then there exists $\delta =\delta (\epsilon ,\alpha )$ such that X can be partitioned as

$$\begin{aligned} X=F\sqcup Y_1\sqcup \cdots \sqcup Y_k \end{aligned}$$

where the graphs $Y_i$ are $\delta$-expanders and are $(\frac{1}{2}-\alpha )$-big in X.

Proof

Let F be an $\alpha$-small maximal $\epsilon$-Følner set and let $Y:=X\smallsetminus F$. If $A\subset Y$ is an $\epsilon$-Følner set of Y, then by Lemma 2.1 we must have:

$$\begin{aligned} |A|>\frac{1}{2}|X|- |F|=|Y|-\frac{1}{2}|X|>\Big (1-\frac{1}{2(1-\alpha )}\Big )|Y|=\frac{1}{2} \Big (\frac{1-2\alpha }{1-\alpha }\Big )|Y|. \end{aligned}$$

That is, Y has no $\frac{1}{2} \Big (\frac{1-2\alpha }{1-\alpha }\Big )$-small $\epsilon$-Følner sets. We can hence apply Theorem A to obtain a partition of Y into $\delta$-expanders. $\square$

Corollary 2.3

Let $(X_n)_{n\in \mathbb {N}}$ be a sequence of finite graphs with $\deg (X_n)\le D$ and $|X_n|\rightarrow \infty$. Given a constant $\epsilon >0$, either there exist $\epsilon$-Følner sets $F_n\subset X_n$ such that $\limsup \frac{|F_n|}{|X_n|}=\frac{1}{2}$ or there exist $\alpha ,\delta >0$ and $\alpha$-big subgraphs $Y_n\subseteq X_n$ that are $(\delta ,D)$-expanders (these options are non-exclusive).

Note in particular that the graphs $Y_n$ in Corollary 2.3 would be a family of expander graphs. A sample application of this result could be proving that some metric space Y contains families of expanders: it may be possible to prove that Y contains some graphs $X_n$ that do not have Følner sets of size $\approx |X_n|/2$, and Corollary 2.3 would then immediately imply that Y contains some genuine expanders as well. This is relevant e.g. in the study of coarse embeddings into Hilbert spaces [5, 8, 9].

2.2 Invariance under quasi-isometry

Given $L,A>0$, a (L, A)-quasi-isometry is a function between metric spaces $f:(X,d_X)\rightarrow (Y,d_Y)$ such that

$$\begin{aligned} \frac{1}{L} d_X(x,x')-A\le d_Y(f(x),f(x'))\le Ld_X(x,x')+A \end{aligned}$$

for every $x,x'\in X$, and such that for every $y\in Y$ there is an $x\in X$ with $d_Y(f(x),y)\le A$. This notion is a cornerstone of geometric group theory [4].

Connected graphs can be seen as metric spaces where the distance between two vertices is the length of the shortest path connecting them. It is well-known that quasi-isometries preserve expansion. More precisely, one can prove the following lemma (see the proof of [10][Lemma 2.7.5]¹):

Lemma 2.4

For every $\epsilon >0$ there exists an $\eta =\eta (\epsilon ,D,L,A)$ such that if X and Y are connected graphs with degree bounded by D and $f:X\rightarrow Y$ is an (L, A)-quasi-isometry, then for every subset $F\subset Y$ with $|\partial F|\le \eta |F|$ the preimage $T=f^{-1}(F)$ is non-empty and satisfies $|\partial T|\le \epsilon |T|$.

Remark 2.5

The value of $\eta$ degrades exponentially fast as a function of the quasi-isometry constants. The proof in [10][Lemma 2.7.5] works for $\eta =\epsilon D^{- p(L,A)}$ where p is some polynomial.

If $f:X\rightarrow Y$ is an (L, A)-quasi-isometry between graphs, then any two vertices of X that are at distance $L(A+2)$ or more are sent to distinct points in Y. It follows that if X has degree bounded by D then

$$\begin{aligned} |f^{-1}(y)|\le ( \text {cardinality of a ball of radius} L(A+2)) \le D^{L(A+2)+1}. \end{aligned}$$

On the other hand, since every point in Y is within distance A from f(X), it follows that if Y has degree bounded by D then

$$\begin{aligned} |Y|\le D^{A+1}|f(X)|\le D^{A+1}|X|. \end{aligned}$$

Combining these inequalities one can prove the following:

Lemma 2.6

Let X and Y be connected graphs with degree bounded by D and $f:X\rightarrow Y$ an (L, A)-quasi-isometry. For any $\alpha >0$ let $\beta :=D^{-L(A+2)-A-2}\alpha$. Then the preimage of a $\beta$-small subset of Y is $\alpha$-small in X.

The following is now immediate:

Proposition 2.7

For every $\epsilon ,\alpha ,D,L,A>0$ there exist $\eta ,\beta >0$ such that if X and Y are connected graphs with degree bounded by D, X has no $\alpha$-small $\epsilon$-Følner set and $f:X\rightarrow Y$ is an (L, A)-quasi-isometry, then Y has no $\beta$-small $\eta$-Følner sets.

We can use Proposition 2.7 and Theorem A to show that the existence of partitions into linearly large expanders is invariant under quasi-isometry. More precisely, we can prove the following:

Theorem 2.8

Fix $\epsilon ,\alpha ,D,L,A>0$ and $\eta ,\beta >0$ as in Proposition 2.7. Let $X_n$ and $Y_n$ be two sequences of finite graphs with degree bounded by D and $f_n:X_n\rightarrow Y_n$ be (L, A)-quasi isometries. If each $X_n$ can be partitioned in $(2\alpha )$-large $\epsilon$-expanders then $Y_n$ can be partitioned into $\beta$-large $\delta$-expanders where $\delta =4^{-\lfloor 1/\beta \rfloor }\eta$.

Proof

Since $X_n$ can be partitioned in $(2\alpha )$-large $\epsilon$-expanders, it does not contain any $\alpha$-small $\epsilon$-Følner set. Proposition 2.7 implies that $Y_n$ does not contain $\beta$-small $\eta$-Følner sets. The claim now follows from Theorem A. $\square$

Remark 2.9

It would be fairly complicated to directly prove Theorem 2.8 by ignoring Theorem A altogether. This is because quasi-isometries are not bijections and the techniques needed to prove Lemmata 2.4 and 2.6 are ill suited for constructing partitions of the codomains.

3 Proof of Theorem A

Recall that, given subsets $A,B\subset X$, we denote by $\partial ^BA$ the set of edges in X joining a vertex in A with a vertex in $B\smallsetminus A$. Define the Cheeger constant of a finite graph as

$$\begin{aligned} h(X):=\min \{{\frac{{|\partial A|}}{{|A|}}} \big | A\subset X,\ 0<{|A|}\le {\frac{1}{2}} {|X|} \}. \end{aligned}$$

Note that X is an $\epsilon$-expander if and only if $h(X)>\epsilon$.

Lemma 3.1

Given any $\epsilon >0$ and a graph X with Cheeger constant $h:=h(X)\le \frac{\epsilon }{2}$, let $Y\subset X$ be a set with $0<|Y|\le \frac{1}{2}|X|$ and $\frac{|\partial Y|}{|Y|}=h$. Then every $(\epsilon /4)$-Følner set of Y is an $\epsilon$-Følner set of X.

Furthermore, letting $Z:=X\smallsetminus Y$ we also have that every $(\epsilon /4)$-Følner set of Z is an $\epsilon$-Følner set of X.

Proof

Let $A\subset Y$ be a set such that $|\partial ^XA|>\epsilon |A|$, we need to show that it is not an $(\epsilon /4)$-Følner set of Y. Note that $\partial ^XA=\partial ^YA\sqcup \partial ^ZA$ and that $\partial ^ZA\subset \partial ^XY$. We have:

$$\begin{aligned} \partial ^X (Y\smallsetminus A)= (\partial ^X Y\smallsetminus \partial ^Z A) \sqcup (\partial ^A (Y\smallsetminus A)), \end{aligned}$$

and hence

$$\begin{aligned} |\partial ^X(Y\smallsetminus A)| = |\partial ^X Y|-|\partial ^Z A| +|\partial ^A (Y\smallsetminus A)| = |\partial ^X Y|-|\partial ^Z A|+ |\partial ^Y A| \end{aligned}$$

because $\partial ^Y A=\partial ^A (Y\smallsetminus A)$. By minimality, we thus obtain:

$$\begin{aligned} h=\frac{|\partial ^X Y|}{|Y|}\le \frac{|\partial ^X (Y\smallsetminus A)|}{|Y\smallsetminus A|} = \frac{|\partial ^X Y|-|\partial ^Z A|+ |\partial ^Y A|}{|Y\smallsetminus A|}. \end{aligned}$$

(1)

For convenience, let $t:=|A|/|Y|$ and let $r:=|\partial ^Y A|/|\partial ^X A|$. With the newly introduced notation, (1) becomes:

$$\begin{aligned} h\le \frac{|\partial ^X Y|-(1-r)|\partial ^X A|+ r|\partial ^X A|}{(1-t)|Y|} =\frac{h}{1-t}+ \frac{2r-1}{(1-t)/t}\frac{|\partial ^X A|}{|A|}. \end{aligned}$$

Rearranging the terms we obtain:

$$\begin{aligned} -h\le (2r-1)\frac{|\partial ^X A|}{|A|} \end{aligned}$$

and hence

$$\begin{aligned} r\ge \frac{1}{2}\Big (1-h\frac{|A|}{|\partial ^X A|} \Big ) > \frac{1}{4}, \end{aligned}$$

(2)

where the last inequality follows from the assumptions $h\le \frac{\epsilon }{2}$ and $\frac{|\partial ^X A|}{|A|}>\epsilon$. We can therefore conclude that A is not an $(\epsilon /4)$-Følner set of Y because

$$\begin{aligned} |\partial ^Y A|=r|\partial ^X A|>\frac{1}{4}|\partial ^X A| >\frac{\epsilon }{4}|A|. \end{aligned}$$

The proof of the “furthermore” part is similar. As above, let $A\subset Z$ be such that $|\partial ^X A|>\epsilon |A|$. Now there are two possibilities. If $|Z\smallsetminus A|\le \frac{1}{2}|X|$ then we have an analogue of (1):

$$\begin{aligned} h \le \frac{|\partial ^X (Z\smallsetminus A)|}{|Z\smallsetminus A|} = \frac{|\partial ^X Z|-|\partial ^Y A|+ |\partial ^Z A|}{|Z\smallsetminus A|} \end{aligned}$$

and the same argument implies that $\partial ^ZA>\frac{\epsilon }{4}|A|$.

On the other hand, if $|Z\smallsetminus A|>\frac{1}{2}|X|$ then $|Y\sqcup A|<\frac{1}{2}|X|$, and therefore we have

$$\begin{aligned} h \le \frac{|\partial ^X (Y\sqcup A)|}{|Y\sqcup A|} = \frac{|\partial ^X Y|-|\partial ^Y A|+ |\partial ^Z A|}{|Y|+|A|} \le h +\frac{|\partial ^Z A|- |\partial ^Y A|}{|Y|+|A|}, \end{aligned}$$

from which it follows that $|\partial ^Z A|\ge |\partial ^Y A|$ and hence $|\partial ^ZA|>\frac{\epsilon }{2} |A|$. $\square$

Proof of Theorem A. Let X be a finite graph with no $\alpha$-small $\epsilon$-Følner sets. We will show that it can be partitioned as $X=X_1\sqcup \cdots \sqcup X_k$ where $k\le \lfloor \frac{1}{\alpha }\rfloor$, all the $X_i$ are $\alpha$-big and they are $\delta$-expanders for $\delta :=\frac{\epsilon }{4^k}$. The idea is to apply Lemma 3.1 recursively: if X is not an $\frac{\epsilon }{2}$-expander then $h(X)\le \frac{\epsilon }{2}$ and there exists a $Y_0\subset X$ that realizes the Cheeger constant. Since X has no $\alpha$-small $\epsilon$-Følner sets, we deduce that $|Y_0|\ge \alpha |X|$. Letting $Y_1:=X\smallsetminus Y_0$, we have a partition $X=Y_0\sqcup Y_1$ where both $Y_i$ are $\alpha$-large. Importantly, it follows from Lemma 3.1 that $\frac{\epsilon }{4}$-Følner sets of $Y_i$ are also $\epsilon$-Følner sets of X. Let us now focus on $Y_0$: if it is an $\frac{\epsilon }{2\cdot 4}$-expander there is nothing to do. Otherwise, we can choose $Y_{00}\subset Y_0$ realizing the Cheeger constant. Such $Y_{00}$ is an $\frac{\epsilon }{4}$-Følner set in $Y_0$ and hence an $\epsilon$-Følner set in X. It follows that $|Y_{00}|\ge \alpha |X|$. On the other hand, $Y_{01}:=Y_0\smallsetminus Y_{00}$ is at least as large as $Y_{00}$ and hence $|Y_{01}|\ge \alpha |X|$. Using Lemma 3.1 we deduce that the partition $Y_0=Y_{00}\sqcup Y_{01}$ is such that every $\frac{\epsilon }{4^2}$-Følner set in $Y_{0i}$ is an $\frac{\epsilon }{4}$-Følner set in $Y_{0}$ and hence an $\epsilon$-Følner set in X. One can thus continue to partition the sets $Y_{i_0i_1\cdots i_k}$ that appear using this procedure. This process ends because X is a finite graph and all the subsets $Y_{i_0i_1\cdots i_k}$ obtained during this process are $\alpha$-big in X. In particular, when the process ends one has partitioned X into at most $\lfloor \frac{1}{\alpha }\rfloor$ sets $X_1,\ldots ,X_k$. Moreover, the worst possible expansion constant is what is obtained by the longest chain of consecutive applications of Lemma 3.1. This gives rise to the—rather generous—lower bound $\delta \ge \frac{\epsilon }{4^k}$.

Remark 3.2

By examining the end of the proof of Theorem A, we see that the natural lower bound on $\delta$ is actually $\frac{\epsilon }{2\cdot 4^{k-1}}$. With some extra care, it is further possible to improve this to $\frac{\epsilon }{4^{k-1}}$ (if the partition process goes all the way and produces k components, then they must automatically be $\epsilon /{4^{k-1}}$ expanders as any $\epsilon /{4^{k-1}}$-Følner set should be $\alpha$-large in X and hence take more than half of the graph). It is also possible to improve the base of the exponential, making it arbitrarily close to $\frac{1}{2}$ (instead of $\frac{1}{4}$). This is accomplished by modifying the statement of Lemma 3.1: Inequality (2) shows that tighter control on h directly yields a better asymptotic behaviour. The optimal parameters for Lemma 3.1 would then depend on the expected value on k. However, such a fine tuning seems unnecessary, as there are other arguments that yield polynomial estimates (see below).

Remark 3.3

As already remarked, Theorem A follows easily from a result of Oveis Gharam–Trevisan. For every $m\ge 1$ one can define a higher order Cheeger constant $\rho _m(X)$ as

$$\begin{aligned} \rho _m(X):=\min \{ \max _{1\le i\le m} \frac{|\partial A_i|}{|A_i|}\Big |A_1,\ldots , A_m\subset X\text { disjoint}\}. \end{aligned}$$

[3][Theorem 1.5] implies that when $\rho _m(X)>0$ one can always find a partition $X=X_1\sqcup \cdots \sqcup X_l$ for some $l\le m-1$ where the graphs $X_i$ are $\zeta$-expanders for some $\zeta =\zeta (m,\rho _m(X),\deg (X))$. To prove Theorem A it is then enough to note that if there are no $\alpha$-small $\epsilon$-Følner sets in X and $m=\lfloor \frac{1}{\alpha }\rfloor +1$, then for any choice of m disjoint sets $A_1,\ldots ,A_m$ at least one of them will be smaller than $\alpha |X|$ and hence $\rho _m(X)>\epsilon$. It will hence be possible to partition X into at most $\frac{1}{\alpha }$-many $\zeta$-expanders.

The proof of Oveis Gharam–Trevisan appears to be somewhat more involved than the proof we gave (it follows from [3][Theorem 1.7]), but it has a few significant advantages: it gives a bound on the number of edges connecting the sets in the partition, it applies to weighted graphs² and it produces asymptotically better constants.

With regard to constants: we wrote that the constant $\zeta$ of Oveis Gharam–Trevisan depends on the degree of X because what they actually estimate is the conductance³ In particular, this makes it hard to compare directly the constants that we obtain. It appears that our approach provides sharper estimates when k is very small (i.e. for large $\alpha$). On the other hand, our estimate degrades exponentially fast with k, while that of Oveis Gharam–Trevisan degrades only quadratically.

One small advantage of our proof is that it is not immediately clear from the result of Oveis Gharam–Trevisan that all the sets $X_1,\ldots , X_l$ appearing in the partition are $\alpha$-big.